题目链接：

---

 

大概自己YY了个贪心然后过了...

二分答案，考虑如何check：

找到一个最小的矩形使得没有覆盖过的点都在这个矩形内，然后猜一下(显然)我要选择的${L*L}$的正方形一定是和这个矩形的某一个顶点公共这个顶点的。

这就好办了，直接枚举正方形的顶点在矩形的$4$个顶点中的哪一个，搜索即可。

复杂度:${O(4^{3}n*log_{2}^{(1e9)})}$

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 using namespace std; 9 #define maxn 10001010 #define inf 0x7fffffff11 #define llg int12 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);13 llg n,m,lx,ly,rx,ry,mid;14 bool bj[maxn],pd;15 16 struct node17 {18 llg x,y;19 }po[maxn];20 21 void find_max()22 {23 lx=inf; ly=-inf;24 rx=-inf; ry=inf;25 for (llg i=1;i<=n;i++)26 if (!bj[i])27 {28 lx=min(lx,po[i].x); rx=max(rx,po[i].x);29 ly=max(ly,po[i].y); ry=min(ry,po[i].y);30 }31 }32 33 void ss(llg cs)34 {35 if (pd) return ;36 find_max();37 llg LX=lx,LY=ly,RX=rx,RY=ry;38 if (lx==inf) {pd=true; return ;}39 if (cs>=4) return ;40 for (llg k=1;k<=4;k++)41 {42 llg x,y;43 if (k==1) x=LX,y=LY;44 if (k==2) x=RX,y=RY;45 if (k==3) x=LX,y=RY;46 if (k==4) x=RX,y=LY;47 vector
            
             c;48 c.clear();49 for (llg i=1;i<=n;i++)50 if (abs(po[i].x-x)<=mid && abs(po[i].y-y)<=mid && !bj[i])51 {52 bj[i]=1;53 c.push_back(i);54 }55 ss(cs+1);56 llg w=c.size();57 for (llg i=0;i
             
              >n;72 for (llg i=1;i<=n;i++) scanf("%d%d",&po[i].x,&po[i].y);73 llg l=0,r=1e9,ans;74 while (l<=r)75 {76 mid=(l+r)>>1;77 if (check()) {r=mid-1; ans=mid;} else l=mid+1;78 }79 cout<
             
            
           
          
         
        
       
      
     

 

---