题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1052
大概自己YY了个贪心然后过了...
二分答案，考虑如何check：
找到一个最小的矩形使得没有覆盖过的点都在这个矩形内，然后猜一下(显然)我要选择的${L*L}$的正方形一定是和这个矩形的某一个顶点公共这个顶点的。
这就好办了，直接枚举正方形的顶点在矩形的$4$个顶点中的哪一个，搜索即可。
复杂度:${O(4^{3}n*log_{2}^{(1e9)})}$
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<cmath>
#include<cstring>
using namespace std;
#define maxn 100010
#define inf 0x7fffffff
#define llg int
#define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
llg n,m,lx,ly,rx,ry,mid;
bool bj[maxn],pd; struct node
{
llg x,y;
}po[maxn]; void find_max()
{
lx=inf; ly=-inf;
rx=-inf; ry=inf;
for (llg i=;i<=n;i++)
if (!bj[i])
{
lx=min(lx,po[i].x); rx=max(rx,po[i].x);
ly=max(ly,po[i].y); ry=min(ry,po[i].y);
}
} void ss(llg cs)
{
if (pd) return ;
find_max();
llg LX=lx,LY=ly,RX=rx,RY=ry;
if (lx==inf) {pd=true; return ;}
if (cs>=) return ;
for (llg k=;k<=;k++)
{
llg x,y;
if (k==) x=LX,y=LY;
if (k==) x=RX,y=RY;
if (k==) x=LX,y=RY;
if (k==) x=RX,y=LY;
vector<llg>c;
c.clear();
for (llg i=;i<=n;i++)
if (abs(po[i].x-x)<=mid && abs(po[i].y-y)<=mid && !bj[i])
{
bj[i]=;
c.push_back(i);
}
ss(cs+);
llg w=c.size();
for (llg i=;i<w;i++) bj[c[i]]=;
}
} bool check()
{
pd=false;
ss();
return pd;
} int main()
{
yyj("bzoj1052");
cin>>n;
for (llg i=;i<=n;i++) scanf("%d%d",&po[i].x,&po[i].y);
llg l=,r=1e9,ans;
while (l<=r)
{
mid=(l+r)>>;
if (check()) {r=mid-; ans=mid;} else l=mid+;
}
cout<<ans;
return ;
}