AOJ 1194: Vampire

上側の点と下側の点の扱い方をつかむまで時間がかかった。幾何は難しい。

問題はこちら。

問題

半径rの太陽が地平線(x軸)からのぼってくる。地平線にはいくつかのビルが建っており、太陽を遮ぎってくれる。いつまでビルによって太陽を完全に遮ることができるかを答える。

解法

問題の図を見ると、ある座標にビルの角と地面（または2つの高さの異なるビルの角）がある場合がある。太陽は下から上ってくるので、重要なのは下側の角である。よって、ある座標を見たとき2つの角があるときは低い方を取っていけばいい。太陽がある高さで遮られないときは、1つ以上のビルの角が太陽の円の内部にあるときである。そして、太陽がどこまでのぼれるかは二分探索で調べればいい。このとき上限値の初期値をh[0]-rとせず、適当に20などとしておくと、太陽がビルの上側までのぼってしまい、ループ中の判定に引っかからなくなってしまう。自分はここで詰まってしまったので、値の変域がきちんと条件と合っているかどうかを確認しないといけない。

while 1:
    r,n = map(int,raw_input().split())
    if r == 0: break

    h = {i:0 for i in xrange(-21,21)}
    for loop in xrange(n):
        xl,xr,hi = map(int,raw_input().split())
        for i in xrange(xl,xr):
            h[i] = max(h[i],hi)

    for i in xrange(20,-21,-1):
        h[i] = min(h[i-1],h[i])

    y,d,u = 0,-r,h[0]-r
    for loop in xrange(30):
        if any(x**2+(y-h[x])**2 < r**2 for x in xrange(-20,21)):
            u = y
        else:
            d = y
        y = (d+u)/2.
    print "%.4f"%abs(y+r)