SRM541 Div1 250

問題

デカルト座標のxまたはyが整数のところをN匹の蟻が動いている。
各蟻はNWESの方向へ一定速度で動いている。
もし衝突した場合は互いに消滅してしまう。

各蟻の初期位置と方向が与えられるとき、最終的に消滅せずに残っている蟻の数を返せ。

考え方

一定間隔で各蟻をずらしながら衝突するかどうかを確認すればよい。

(0,0,N)と(0,1,S)の蟻は(0,0.5)で衝突する場合があるように、0.5刻みで動かせばよい。
(小数は扱いたくないので、座標を2倍にした)

一番遅く衝突する可能性があるのは、(-1000,1000,E)と(1000,-1000,N)とかの場合なので、0.5刻みを4000回ぐらいやればよい。

xとyが-10^9から10^9までだったら、各蟻が衝突する可能性のある蟻を調べて、一番衝突するのが早い時間、、のように刻み幅を変えればよさそう？