思路：
二分答案；
二分可能的长度；
然后递归判断长度是否可行；
先求出刚好覆盖所有点的矩形；
可行的第一个正方形在矩形的一个角上；
枚举四个角上的正方形，然后删去点；
删去一个正方形后，递归求出删去一个正方形后的矩形；
往复三次，判断三次删点能否全部删光；
代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; #define maxn 20005
#define INF 0x7ffffff int n,maxnlen=,upx,upy,downx,downy;
int aix[maxn],aiy[maxn],maxlen,if_[maxn]; inline void in(int &now)
{
int if_z=;now=;
char Cget=getchar();
while(Cget>''||Cget<'')
{
if(Cget=='-') if_z=-;
Cget=getchar();
}
while(Cget>=''&&Cget<='')
{
now=now*+Cget-'';
Cget=getchar();
}
now*=if_z;
} bool thcheck(int len)
{
int upx_=INF,upy_=-INF,downx_=-INF,downy_=INF;
for(int i=;i<=n;i++)
{
if(if_[i]==||if_[i]==) continue;
if(aix[i]<upx_) upx_=aix[i];
if(aiy[i]>upy_) upy_=aiy[i];
if(aix[i]>downx_) downx_=aix[i];
if(aiy[i]<downy_) downy_=aiy[i];
}
if(max(downx_-upx_,upy_-downy_)<=len) return true;
else return false;
} bool secheck(int len)
{
int upx_=INF,upy_=-INF,downx_=-INF,downy_=INF;
for(int i=;i<=n;i++)
{
if(if_[i]==) continue;
if(aix[i]<upx_) upx_=aix[i];
if(aiy[i]>upy_) upy_=aiy[i];
if(aix[i]>downx_) downx_=aix[i];
if(aiy[i]<downy_) downy_=aiy[i];
}
upx_=upx_+len,downx_=downx_-len,upy_=upy_-len,downy_=downy_+len;
for(int i=;i<=n;i++)
{
if(if_[i]==) continue;
if(aix[i]<=upx_&&aiy[i]>=upy_) if_[i]=;
}
if(thcheck(len)) return true;
for(int i=;i<=n;i++)
{
if(if_[i]==) continue;
if(aix[i]<=upx_&&aiy[i]<=downy_) if_[i]=;
else if_[i]=;
}
if(thcheck(len)) return true;
for(int i=;i<=n;i++)
{
if(if_[i]==) continue;
if(aix[i]>=downx_&&aiy[i]>=upy_) if_[i]=;
else if_[i]=;
}
if(thcheck(len)) return true;
for(int i=;i<=n;i++)
{
if(if_[i]==) continue;
if(aix[i]>=downx_&&aiy[i]<=downy_) if_[i]=;
else if_[i]=;
}
if(thcheck(len)) return true;
else return false;
} bool check(int len)
{
for(int i=;i<=n;i++) if_[i]=;
int upx_=upx+len,downx_=downx-len,upy_=upy-len,downy_=downy+len;
for(int i=;i<=n;i++) if(aix[i]<=upx_&&aiy[i]>=upy_) if_[i]=;
if(secheck(len)) return true;
for(int i=;i<=n;i++)
{
if(aix[i]<=upx_&&aiy[i]<=downy_) if_[i]=;
else if_[i]=;
}
if(secheck(len)) return true;
for(int i=;i<=n;i++)
{
if(aix[i]>=downx_&&aiy[i]>=upy_) if_[i]=;
else if_[i]=;
}
if(secheck(len)) return true;
for(int i=;i<=n;i++)
{
if(aix[i]>=downx_&&aiy[i]<=downy_) if_[i]=;
else if_[i]=;
}
if(secheck(len)) return true;
else return false;
} int main()
{
in(n);
upx=INF,upy=-INF;
downx=-INF,downy=INF;
for(int i=;i<=n;i++)
{
in(aix[i]),in(aiy[i]);
if(aix[i]<upx) upx=aix[i];
if(aiy[i]>upy) upy=aiy[i];
if(aix[i]>downx) downx=aix[i];
if(aiy[i]<downy) downy=aiy[i];
}
maxlen=max(upy-downy,downx-upx);
int l=,r=maxlen,ans=0x7fffffff;
while(l<=r)
{
int mid=l+r>>;
if(check(mid)) ans=mid,r=mid-;
else l=mid+;
}
cout<<ans;
return ;
}