F – Dist Max 2

题目描述：

给你n个点，求 max{min(|xi - xj|, |yi-yj|)},1 <= i,j <= n

思路：

显然是二分答案，但是check怎么写？

这里是有一点二维偏序的意思在里面，我们按照x从小到大排序，再此基础上，check(mid)的时候，遍历整个数组，维护一个minx,一个maxn，表示在这之前出现过的满足x的差值大于等于mid的y的最小值和最大值，用一个队列存下来还没产生贡献的点，然后对于遍历到的点，先去看看能不能继续更新minx 和maxn，然后把这个点塞进去，如果发现哪次 $maxn - tr[i].y >= mid || tr[i].y - minx >= mid$ 就return true

这里用的是逆序的思维，一般来说我们想到的都是后面的对当前的产生的贡献，如果是这么想，就很难写check函数，但如果逆着想，会发现计算当前点对这之前的点产生的贡献，是很容易的，因为你可以维护出了minx和maxn

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

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m;
struct ran{
    int x, y;
    bool operator < (const ran &a)const{
        if(x != a.x)return x < a.x;
        else return y < a.y;
    }
}tr[MAX];


bool check(int mid){
    queue<ran>q;
    int minx = inf, maxn = 0;
    for(int i = 1; i <= n; ++i){
        while (!q.empty() && tr[i].x >= q.front().x + mid) {
            minx = min(minx, q.front().y);
            maxn = max(maxn, q.front().y);
            q.pop();
        }
        if(maxn - tr[i].y >= mid || tr[i].y - minx >= mid)return true;
        q.emplace(tr[i]);
    }
    return false;
}

void work(){
    cin >> n;
    for(int i = 1; i <= n; ++i)cin >> tr[i].x >> tr[i].y;
    sort(tr + 1, tr + 1 + n);
    int l = 1, r = inf;
    while (l <= r) {
        int mid = (l + r) / 2;
        if(check(mid))l = mid + 1;
        else r = mid - 1;
    }
    cout << l - 1 << endl;
}


int main(){
    io;
    work();
    return 0;
}