TopCoder SRM 426 Div1 Med: CatchTheMice

SRM練習会に参加。はじめてDiv1のMedを自力で解けたが、1度再提出しないといけなかったので要反省だ。

問題

おもちゃのネズミをカゴで捕まえるゲームがある。
2次元平面の地面にN(≦ 50)匹のおもちゃのネズミがあり、それぞれ初期位置と速度が決まっている。ゲームが開始すると、ネズミは等速直線運動をはじめるとする。
ネズミを捕まえるカゴは一辺Lの正方形で、カゴの位置は自由に動かせるが、その一辺はx軸と常に平行でないといけない。
任意のタイミングでカゴを地面におろすことができる。どのタイミングでもすべてのネズミを捕まえられないようなカゴの大きさの最大値を答えよ。

解法

二分探索、または三分探索で解くことができる。自分は時間tに対して三分探索で解いたので、そちらの解法を説明していく。

ある時間のネズミをすべて捕まえるのに必要なカゴの大きさは、一番左側と右側のネズミの距離と一番上側と下側のネズミの距離の大きい方となる。
またあるネズミのペアの時間tに対するx(y)方向の距離のグラフは直線またはVの字になる。すべてのペアに対してのグラフを書き重ねていくと下に凸（または直線）のグラフとなる。
したがって時間lと時間rについて必要なカゴの大きさを比べ、大きい方について範囲を狭めていく三分探索を行えば答えを得ることができる。

def largestCage(self, xp, yp, xv, yv):
    N = len(xp)
    low, high = 0, inf
    ans = inf
    for loop in xrange(1000):
        l = (2 * low + high) / 3.0
        r = (low + 2 * high) / 3.0
        lx1, rx1, dy1, uy1 = inf, -inf, inf, -inf
        for i in xrange(N):
            lx1 = min(lx1, xp[i] + xv[i] * l)
            rx1 = max(rx1, xp[i] + xv[i] * l)
            dy1 = min(dy1, yp[i] + yv[i] * l)
            uy1 = max(uy1, yp[i] + yv[i] * l)
        
        lx2, rx2, dy2, uy2 = inf, -inf, inf, -inf
        for i in xrange(N):
            lx2 = min(lx2, xp[i] + xv[i] * r)
            rx2 = max(rx2, xp[i] + xv[i] * r)
            dy2 = min(dy2, yp[i] + yv[i] * r)
            uy2 = max(uy2, yp[i] + yv[i] * r)

        L1 = max(rx1 - lx1, uy1 - dy1)
        L2 = max(rx2 - lx2, uy2 - dy2)
        if L1 <= L2:
            high = r
        else:
            low = l
        ans = min(ans, L1, L2)

    return ans