M-SOLUTIONS プロコンオープン 2020 F. Air Safety

問題

現在、各飛行機が(X_i, Y_i)を飛行しており、x,y座標を正か負の方向に進んでいる。
すべての飛行機は秒速0.1で進んでおり、同時刻に同じ座標に来てしまうと衝突してしまう。

飛行機の中で、一番早く衝突してしまう飛行機が衝突までの何秒かを求めよ。
衝突する飛行機がない場合は、SAFEと答えよ。

制約

• 1 <= N <= 200000
• 0 <= X_i, Y_i <= 200000, X_i,Y_iは整数
• 方向U_i = U, R, D, L
• 飛行機の位置(X_i, Y_i)はすべて異なる

解法

衝突する可能性があるのは、左右からぶつかってくる場合と真正面からぶつかってくる場合が考えられる。

まず、真正面からぶつかってくる場合を考える。
x座標とy座標で、同じ座標で、UとD、LとRのペアは衝突する可能性がある。
しゃくとりのように、ソートして、小さい方からRのものより大きい一番近いLのものについて、距離がDだった場合は、D*10/2秒後に衝突する。

次に、左右からぶつかってくる場合を考える。
RのものとDのものを考えると、Rのものが(x_i, y_i)で、Dのものが(x_j, y_j)とすると、x_j-x_i=y_j-y_iの場合に衝突する。
これを移項すると、x_j-y_j = x_i-y_iなので、Dに進む(x_j, y_j)のうち、x_j-y_jがx_i-y_iと一致する飛行機だけを考えればよい。
したがって、x_i-y_iをそれぞれもとめて、一致するものについて考える。
一致するものについて、RとDの飛行機をx座標でソートすると、しゃくとりのように処理すればO(N)で一番近い衝突する飛行機がわかり、(x_j - x_i)*10秒後に衝突するのがわかる。

また、RのものとUのものを考えると、Rのものが(x_i, y_i)で、Uのものが(x_j, y_j)とすると、x_j-x_i=y_i-y_jの場合に衝突するので、移行するとx_i+y_i=x_j+y_jのものなので、上記と同様に一致するものについて考えれば良い。

さらに、LとD、LとUについて同様の処理をすればよい。

ただし、この4パターンをそれぞれ別々に処理を書くとかなり行数になってしまったり、コピペコードだと修正漏れなどわかりにくいバグを埋め込みやすくなってしまう。
これについては、各座標について、反転や回転を行うと「RとDの場合」と等価な処理にできるので、実装量を減らせる。