这道题的思路挺简单的……就是可以证明如果要覆盖一个区域内的点，那么一定有一个正方形在这“区域内的点所围成的最大矩形的四个角中的一个”（不要吐槽很多的“的”……），对于长度r是否可以覆盖整个区域内的点，只需要先枚举第一个矩形在“区域内的点所围成的最大矩形的四个角中的哪一个”，然后再枚举下一个点在“区域内的剩余点所围成的最大矩形的四个角中的哪一个”第三个正方形就直接判断余下的点的最大最小差值是否小于r就行了……再然后就直接二分答案了……然后，注意一种情况，就是出现一个或者两个矩形就可以覆盖完整个区域点的情况（可能是因为我傻×于是就被这里坑了一下）……

 

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384type  arr=record    x,y:longint;  end;var  a:array[0..250000]of arr;  i,j,k,l,r,n,mid,maxx,minx,maxy,miny:longint;  vs:array[0..250000]of longint; procedure find(var x1,x2,y1,y2:longint);begin  x1:=-maxlongint;  x2:=maxlongint;  y1:=-maxlongint;  y2:=maxlongint;  for i:=1 to n do if vs[i]=0 then    begin      if a[i].x>x1 then x1:=a[i].x;      if a[i].x
      
       y1 then y1:=a[i].y;      if a[i].y
       
        =a[i].x) and (miny+x>=a[i].y) then vs[i]:=y;  if dfs(x,y+1) then exit(true);  for i:=1 to n do    if vs[i]=y then vs[i]:=0;   for i:=1 to n do    if vs[i]=0 then      if (minx+x>=a[i].x) and (maxy-x<=a[i].y) then vs[i]:=y;  if dfs(x,y+1) then exit(true);  for i:=1 to n do    if vs[i]=y then vs[i]:=0;   for i:=1 to n do    if vs[i]=0 then      if (maxx-x<=a[i].x) and (miny+x>=a[i].y) then vs[i]:=y;  if dfs(x,y+1) then exit(true);  for i:=1 to n do    if vs[i]=y then vs[i]:=0;   for i:=1 to n do    if vs[i]=0 then      if (maxx-x<=a[i].x) and (maxy-x<=a[i].y) then vs[i]:=y;  if dfs(x,y+1) then exit(true);  for i:=1 to n do    if vs[i]=y then vs[i]:=0;  exit(false);end; begin  readln(n);  for i:=1 to n do    readln(a[i].x,a[i].y);  fillchar(vs,sizeof(vs),0);  find(maxx,minx,maxy,miny);  l:=1;  if maxx-minx>maxy-miny    then r:=maxx-minx    else r:=maxy-miny;  while l<=r do begin    fillchar(vs,sizeof(vs),0);    mid:=(l+r)>>1;    if dfs(mid,1) then r:=mid-1      else l:=mid+1;  end;  writeln(l);  readln;end.