Location for a Power Generator (UVa Live Archive Asia - 2009 Hsinchu(Taiwan))

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=350&page=show_problem&problem=2531

問題

携帯型原子力発電機で街の各家庭に電力を供給したい。発電機からの距離がl以下の時にその家には電力が供給される。1台の発電機で同時に電力を供給できる家庭の数と、その場所の選び方の数を答えよ。
家の数<=1100

解法

要するに、なるべく多くの点を含む円を見つければ良い。これは極座標平面での平面走査を使えばO(n^2logn)で求めることができる。
具体的には、ある点iを極座標の中心として、点iからl離れた円周上で円を動かすことを考える。こうすると点jは角度θで円に入り、θ'で円から出ると計算できる。全てのjでこれを計算し角度をソートしてどの点が円に入っているかを計算すればO(nlogn)で点iについての計算ができる。
場所の選び方の数は実際に円に入っている点の集合を全て列挙すれば良い。
最後に無駄な改行を入れないとWAになるので注意。