最小値の最大化は二分探索で解けることが多いです。

まず距離が \(K\) 以上の点のペアが存在するか？という判定問題の解法を考えてみましょう。

• \(\min(|x_i - x_j|, |y_i - y_j|) \geq K \)

を同値変形すると、

• \(|x_i - x_j| \geq K\) かつ \(|y_i - y_j| \geq K\)

となります。よって、距離が \(K\) 以上の点対が存在するための条件は以下の通りです。

ある点 \((x_i,y_i)\) に対して、\(x\) 座標が \(x_i-K\) 以下の点の \(y\) 座標の最小値が \(y_i-K\) 以下または最大値が \(y_i+K\) 以上

これはあらかじめ点を \(x\) 座標でソートしておくことにより、尺取り法を使って \(O(N)\) で判定することができます。

したがって、答えで決め打ち二分探索をすると全体の計算量は \(O(N\log N+N\log \max(x_i))\) となります。

実装例 (C++)

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n; cin >> n;
    vector<pair<int,int>> v(n);
    for(int i = 0; i < n; i++) cin >> v[i].first >> v[i].second;
    sort(v.begin(), v.end());
    int ok = 0, ng = 1000000001;
    while(ng - ok > 1){
        int md = (ok + ng)/2;
        queue<pair<int,int>> que;
        bool able = false;
        int mi = 1000000001, ma = 0;
        for(auto p:v){
            while(!que.empty()){
                if(que.front().first > p.first - md)break;
                mi = min(mi, que.front().second); ma = max(ma, que.front().second);
                que.pop();
            }
            if(mi <= p.second - md || ma >= p.second + md) able=true;
            que.push(p);
        }
        if(able) ok = md;
        else ng = md;
    }
    cout << ok << endl;
}