点集合を \((x_i, y_i)\) の辞書順で昇順にソートします．すなわち，任意のペア \((i, j)\) \((i < j)\) に対して，\(x_i < x_j\) または [ \(x_i = x_j\) かつ \(y_i < y_j\) ] が成り立つとします．

最大を達成するペア \((i, j)\) \((i < j)\) が \(x_i < x_j\), \(y_i < y_j\) を満たす場合を考えましょう．\(x_i < x_j\), \(y_i > y_j\) の場合については，\(y\) 座標をすべて \(-1\) 倍してから同じことをすればよいです．

点を添字順に処理していきます．\(j\) 番目の点 \((x_j, y_j)\) を処理するときには，既に処理済みの \(i \ (< j)\) であって，\(x_i < x_j\) かつ \(y_i < y_j\) を満たすもののうち，\(j\) との距離が最大になるものを見つけたいです．そのために，処理済みの点の \(x\) 座標ごとの \(y\) 座標の最小値を，\(y\) 座標の値が単調減少になるように（ \(x_{i'} > x_i\) かつ \(y_{i'} > y_i\) となる \(i' > i\) は不要なので追加しないように）管理しておきます．これは，\(x\) 座標が単調増加かつ \(y\) 座標が単調減少なので，配列の末尾に追加していくだけで可能です．その配列の中で，\(x\) 側が距離を達成する点（後半に固まっている）と \(y\) 側が距離を達成する点（前半に固まっている）の境界を二分探索で求めれば，その両側のいずれかが欲しい値を達成しています．

最初のソートと毎回の二分探索がボトルネックになり，全体の計算量は \(\mathrm{O}(N \log N)\) です．