ARC121 A 2nd Greatest Distance
x軸方向とy軸方向に分けて考える
.
$ x
座標,
$ y
座標を昇順にソートしてみる(その際, indexも保持しておく). すると, 降順でチェビシェフ距離が2番目のものの候補は,
$ x
座標について
$ 3
通り,
$ y
座標について
$ 3
通りの合計
$ 6
通りしかなく, すべて試すことができる. よってこの問題を
$ O(N \log N)
で解くことができた.
実装例:
https://atcoder.jp/contests/arc121/submissions/22990096