Forests

http://acm.uva.es/p/v1/149.html

整数座標に無限に木が立ってて、ある地点から見える木の数を求めろという問題。ある木が「見える」というのは、その木の両端が直接見えて、かつ、他の任意の木との隙間の角度が0.01度以上ある場合のことを言うと。木は完全な円で、半径が与えられる。

まず何気に円の接線出そうしてはまったのは秘密。それで角度だけ分かれば良いと。円の中心は分かってるので、観察地点と、円の中心と、観察地点から伸びる円の接線の接点（？）の三つの点でなす直角三角形から、観察地点と二つの接点を結ぶ直線と、x軸がなす角度が分かるので、それを求めまくってかぶってないか比較すれば良い。

しかしこの問題、座標が無限にあるので、全然処理が終わらない。それで諦めたのが昨日の夜だったんだけど、今日になって色々試して見たら、x、yともに-30~30くらいの範囲だけ調べれば大丈夫なことを発見したので一気にsubmit immediately!!!!うっかりaccept。ktkr。

今100番から順番に解いていってるので、次は152なわけですが、これがサッパリ分からない。最近点対求めろみたいな。連続幾何ですかそうですか。