AtCoder Beginner Contest 215

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;

const int N = 2e5 + 5;

struct Node{
    int x, y;
} a[N];

bool cmp(Node t1, Node t2){
    return t1.x < t2.x;
}

int n;

bool check(int x){
    int maxn = INT_MIN, minn = INT_MAX;
    for(int i = 1, j = 1; i <= n; i++){
        while(j < i && a[i].x - a[j].x >= x){
            maxn = max(maxn, a[j].y);
            minn = min(minn, a[j].y);
            j++;
        }
        if(maxn >= a[i].y + x)return true;
        if(minn <= a[i].y - x)return true;
    }
    return false;
}

int main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i].x >> a[i].y;
    sort(a + 1, a + 1 + n, cmp);
    int L = 0, R = 1e9 + 10;
    while(L + 1 < R){
        int M = (L + R) >> 1;
        if(check(M)) L = M;
        else R = M;
    }
    cout << L << endl;
    return 0;
}