ABC215 F Dist Max 2
ここで, 一方の点$ (x_i, y_i)を全探索し, $ C(k) := 距離が$ k以上となるような点は存在するか？ という判定問題を解くことを考える.
さらに, $ x_i > x_jと仮定する.
すると, 適切な式変形を行うことで, $ C(k) := $ x_j \leq x_i - Kであって, $ y_i + K \leq y_jまたは$ y_j \leq y_i - Kなる$ (x_j, y_j)は存在するか？ と言い換えられる. これは, あらかじめ$ yについて累積MaxとMinを計算しておくことにより高速に判定できる.
よってこの問題を, $ O(N \log N)で解くことができた.