题目
给定一堆点，要求使用三个长为 (L) 的正方形把所有点覆盖，求 (L) 的最小值。
分析
发现只有三个正方形，但是我们如果把四个边界求出来，这样有四个，所以肯定有两个边界同时被一个正方形覆盖吗，也就是一定有一个正方形卡在一个角上。
不妨设这就是第一个，于是我们找出一个最优的角去覆盖即可。
然后去掉覆盖掉的点，同样的，发现对于两个正方形同样有这样的一个性质，必须有一个正方形卡在角上，于是再做一遍，那么最后再求出剩下的可不可以被一个正方形覆盖即可。
代码
#include<bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x){
x=0;bool f=false;char ch=getchar();
while(!isdigit(ch)){f|=ch=='-';ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
x=f?-x:x;
return ;
}
template <typename T>
inline void write(T x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10^48);
return ;
}
const int INF=2e9,N=2e5+5;
int n,x[N],y[N],c[N];
void cover(int X,int Y,int L,int w){for(int i=1;i<=n;i++) if(x[i]>=X&&x[i]<=X+L&&y[i]>=Y&&y[i]<=Y+L) c[i]+=w;}
void GetCover(int&X,int&Y,int&xx,int&yy){
X=Y=INF,xx=yy=-INF;
for(int i=1;i<=n;i++) if(!c[i]) X=min(X,x[i]),xx=max(xx,x[i]),Y=min(Y,y[i]),yy=max(yy,y[i]);
return ;
}
bool Check3(int L){
int x,y,xx,yy;
GetCover(x,y,xx,yy);
if(x==INF) return true;
return xx-x<=L&&yy-y<=L;
}
bool Check2(int L){
int x,y,xx,yy;
GetCover(x,y,xx,yy);
if(x==INF) return true;cover(x,y,L,1);
if(Check3(L)) return true;cover(x,y,L,-1);cover(xx-L,y,L,1);
if(Check3(L)) return true;cover(xx-L,y,L,-1);cover(x,yy-L,L,1);
if(Check3(L)) return true;cover(x,yy-L,L,-1);cover(xx-L,yy-L,L,1);
if(Check3(L)) return true;cover(xx-L,yy-L,L,-1);
return false;
}
bool Check1(int L){
for(int i=1;i<=n;i++) c[i]=0;
int x,y,xx,yy;
GetCover(x,y,xx,yy);cover(x,y,L,1);
if(Check2(L)) return true;cover(x,y,L,-1);cover(xx-L,y,L,1);
if(Check2(L)) return true;cover(xx-L,y,L,-1);cover(x,yy-L,L,1);
if(Check2(L)) return true;cover(x,yy-L,L,-1);cover(xx-L,yy-L,L,1);
if(Check2(L)) return true;cover(xx-L,yy-L,L,-1);
return false;
}
int main(){
read(n);
int Max1=-INF,Max2=-INF,Min1=INF,Min2=INF;
for(int i=1;i<=n;i++){
read(x[i]),read(y[i]);
Max1=max(Max1,x[i]);Min1=min(Min1,x[i]);
Max2=max(Max2,y[i]);Min2=min(Min2,y[i]);
}
if(Check1(0)) return write(0),0;
int l=0,r=max(Max1-Min1,Max2-Min2);
while(l+1<r){
int mid=(l+r)/2;
if(Check1(mid))r=mid;
else l=mid;
}
write(r);
return 0;
}