M-SOLUTIONS プロコンオープン 2020 F - Air Safety (600)
ある飛行機が前を向いているとする
この飛行機と衝突する可能性があるのは、
真っ正面の方向にいてこちら向きの飛行機
左斜め前45度の直線上にいる右向きの飛行機
右斜め前45度の直線上にいる左向きの飛行機
これらの位置に飛行機がいるかを調べれば良い
全ての飛行機間でこの関係を調べると$ O(N^2)で間に合わない
X軸に平衡、Y軸に平衡、左斜め前45度、右斜め前45度の同じ直線上にいる同じ向きの飛行機を集めた集合を持っておく
左斜め前45度の集合は$ x + yが同じ、右斜め前45度の集合は$ x - yが同じ値の集合になる
値の追加に$ O(\log N)かかるので全部追加するのは$ O(N \log N)
それぞれの飛行機で同じ集合にいる内最も近い飛行機の座標をlower_bound/upper_boundで求める
値の探索に$ O(\log N)かかるので全部追加するのは$ O(N \log N)
前処理も探索も同じ計算量なので全体でも$ O(N \log N)