The maximization problem of a minimum value can often be solved with a binary search.

First, let us consider if there is a pair with distance more than or equal to \(K\).

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

is equivalent to

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

so there exists a pair of points with distance more than or equal to \(K\) if and only if:

there exists a point \((x_i,y_i)\) such that the minimum \(y\) coordinates of points with \(x\) coordinates at most \(x_i-K\) is less than or equal to \(y_i-K\), or the maximum \(y\) coordinates of them is more than or equal to \(y_i+K\)

By sorting the points by its \(x\) coordinates firsthand, it can be checked in an \(O(N)\) time using a sliding window.

Therefore, one can do binary search against the answer to solve it in a total of \(O(N\log N+N\log \max(x_i))\) time.

Sample Code (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;
}