【ATC】:Dist Max 2 二分

传送门

题意

给出$n$个点对，求最大的$min(x_i-x_j,y_i-y_j)$

分析

处理这种最小值最大问题，一般都是二分
我们枚举一个$mid$，$check$函数就是要判断是否有两个点满足$min(x_i-x_j,y_i-y_j)>=mid$
我们把所有点按照第一维排序，这样，我们从$1$到$n$一次去扫描这些点，并且处理一个队列，只有当满足$x_i-mid>=x_j$的时候，$j$进入队列，然后维护$y_j$的最大值和最小值即可

代码

#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
#define _CRT_SECURE_NO_WARNINGS
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 10;
const ll mod = 1000000007;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a) {
    char c = getchar(); T x = 0, f = 1; while (!isdigit(c)) {if (c == '-')f = -1; c = getchar();}
    while (isdigit(c)) {x = (x << 1) + (x << 3) + c - '0'; c = getchar();} a = f * x;
}
int gcd(int a, int b) {return (b > 0) ? gcd(b, a % b) : a;}
struct Node {
    int x, y;
} a[N];
int n;

bool cmp(Node A, Node B) {
    if (A.x != B.x)
        return A.x < B.x;
    return A.y < B.y;
}

bool check(int mid) {
    int l = 1,mi = INF,mx = 0;
    for (int i = 1; i <= n; i++) {
        int x = a[i].x - mid;
        while (l <= n && a[l].x <= x) mi = min(mi, a[l].y),mx = max(mx,a[l++].y);
        if (a[i].y - mi >= mid || mx - a[i].y >= mid) return true;
    }
    return false;
}

int main() {
    read(n);
    for (int i = 1; i <= n; i++) read(a[i].x), read(a[i].y);
    sort(a + 1, a + 1 + n, cmp);
    int l = 0, r = INF;
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    di(l);
    return 0;
}