F - Dist Max 2
什么时候我才能突破\(F\)题的大关...
算了，不说了，看题。
简化题意：给定\(n\)个点的坐标，定义没两个点的距离为\(min(|x_i-x_j|,|y_i-y_j|)\)，求所有点对中距离的最大值。其实看到一个最小，一个最大就应该想到二分的...最小值最大或最大值最小，二分答案不是最擅长解决这类问题的吗？但有时候就会想想了，为什么二分答案在这些条件下就十分适用了...考虑最小值最大(或最大值最小)，说明有很多方案，每个方案都有对应的最小值，求所有方案的最大值，显然比最大值小的方案肯定都能实现，那这不就满足答案单调性了吗？再看我们二分答案以后，我们给定一个答案，之后只需判定是否合法就行。这样的话我们还需根据给定的答案去构造一种满足答案的方案即可，这可比解决最优化的问题简单多了。
好了，不多时候了，回到这个题，我们二分一个答案后怎么判断答案是否合法，由于是两维的关系，我门先按\(x\)排序消掉一维，比如说我们二分的答案为\(k\)，那我们考虑每个点向后找其他的点匹配，对于当前点\(i\),显然只有\(x_i+k\)之后的点才能被统计，我们可以将之后的点放到一个set里面，这样就能快速找到合法的\(x\)中是否有合法的\(y\)了。总复杂度\(O(nlog^2n)\)这个复杂度竟然T了，好吧，二分答案的log大概30多，再加上set，确实可能会T，但我们考虑这个set的操作，实际上我们需要查询的就是一个后缀的最小值和最大值，这里发现可以直接预处理，开心的省去一个log，看这次还过不过！！！
//不等,不问,不犹豫,不回头.
#include<bits/stdc++.h>
#define _ 0
#define ls p<<1
#define db double
#define rs p<<1|1
#define P 1000000007
#define ll long long
#define INF 1000000000
#define get(x) x=read()
#define PLI pair<ll,int>
#define PII pair<int,int>
#define ull unsigned long long
#define put(x) printf("%d\n",x)
#define putl(x) printf("%lld\n",x)
#define rep(x,y,z) for(int x=y;x<=z;++x)
#define fep(x,y,z) for(int x=y;x>=z;--x)
#define go(x) for(int i=link[x],y=a[i].y;i;y=a[i=a[i].next].y)
using namespace std;
const int N=2e5+10;
int n,mn[N],mx[N];
struct wy{int x,y;}a[N];
inline int read()
{
int x=0,ff=1;
char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();}
while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*ff;
}
inline bool cmp(wy a,wy b) {return a.x<b.x;}
inline bool check(int k)
{
int r=1;
rep(i,1,n)//为每个左端点找合适的右端点
{
while(r<=n&&a[r].x-a[i].x<k) ++r;
if(r>n) return false;
if(abs(mn[r]-a[i].y)>=k||abs(mx[r]-a[i].y)>=k) return true;
}
return false;
}
int main()
{
//freopen("1.in","r",stdin);
get(n);
rep(i,1,n) get(a[i].x),get(a[i].y);
sort(a+1,a+n+1,cmp);
mn[n+1]=INF*2;mx[n+1]=-INF;
fep(i,n,1) mn[i]=min(mn[i+1],a[i].y),mx[i]=max(mx[i+1],a[i].y);
int l=0,r=INF*2;
while(l<r)
{
int mid=l+r+1>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
put(l);
return (0^_^0);
}
//以吾之血,铸吾最后的亡魂.