二分出 min( | xi - xj | , | yi - yj | ),双指针维护是否存在满足条件的点对(i, j),假如二分当前值是x,那么 |xi - xj| >= x &&|yi - yj| >= x
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#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; }View Code
标签:Node,AtCoder,215,Beginner,minn,int,maxn,xj From: https://www.cnblogs.com/zhujio/p/17659312.html