Fairy Wars (ZOJ Problem Set - 3521)

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3521

問題

アイスバリアを張って弾を止める。まず座標(sx,sy)に半径rのアイスが置かれる。次にアイスと接触している弾はその点を中心としてl×lの正方形のアイスになる。アイスになった弾に接触している弾も連鎖的にアイスになっていく時、何個の弾がアイスになるか求めよ。
弾の数<=50000

座標	<=1000000000

解法

まず敵弾を(l/2)×(l/2)のグリッドに分割する。各グリッドの内部の敵弾が一つアイスになればその中の敵弾は全てアイスになる。なのであるグリッドと周りの8個のグリッドの間でアイスになるかどうかの判定が出来れば良い。左右、上下はもちろんO(m)(mはグリッドの内部の敵弾の数)ででき、斜めの判定もx座標順にソートして尺取メソッドを使えばO(mlogm)で判定可能。なので全体でO(nlogn)で計算可能。