Camera in the Museum (UVa Live Archive Asia - Site 9 (Bangladesh) - 2009/2010)

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4499

問題

奥行きH、幅Wの美術館がある。骨董品を盗まれないようにするため天井に監視カメラを設置したいが、半径Rの円形のオフィスが視線をさえぎってしまう場合がある。骨董品がN個存在しその位置が与えられた時、監視カメラを設置した場合に同時に見ることが出来る骨董品の数は最大何個か？
50<=H,W<=10000
0<2R<10000
N<=10000

解法

骨董品iとオフィスの接線を求め、その半直線と壁との交点を二つ求める。その交点とオフィスの中心からの角度を求めると、片方は(壁沿いに歩いた時の)視線がさえぎられる区間の開始地点、もう一方は終了地点となる。あとは交点を角度順にソートして最も多くの骨董品を見れる区間を探せばよい。