首先可以二分答案，将最优性问题转化为判定性问题。

　　对于二分到的边长，我们可以把所有的点看成一个大的矩形，这个矩形为包括所有点的最小矩形，那么贪心的想，3个正方形，第一个肯定放在这个矩形其中的一角，然后去掉覆盖的点，然后再求出一个矩形，然后再枚举放在哪一角，去掉之后判断剩下的是否可以由一个正方形覆盖就行了。

　　反思：没画图，边界算的不对，而且枚举完两个正方形之后要判下是否没有没覆盖的点了。另外提供神样例 4 1 1 -1 -1 1 -1 -1 1答案是2。

/**************************************************************    Problem: 1052    User: BLADEVIL    Language: C++    Result: Accepted    Time:1484 ms    Memory:1280 kb****************************************************************/ //By BLADEVIL#include 
     
      #include 
      
       #include 
       
        #define maxn 20010#define inf (~0U>>1) using namespace std; struct rec {    int x,y,flag;    rec(){        x=y=flag=0;    }}a[maxn],b[maxn]; int n; bool cmp(rec x,rec y) {    return (x.flag
        
         =left)&&(b[i].y<=up)&&(b[i].y>=down)) b[i].flag=1;} bool work(int i,int j,int x) {    memcpy(b,a,sizeof a);    make(i,x);    sort(b+1,b+1+n,cmp);    make(j,x);    sort(b+1,b+1+n,cmp);    rec MAX,MIN;    update(MAX,MIN);    int left=MIN.x,right=MAX.x,up=MAX.y,down=MIN.y;    //printf("%d %d %d %d %d\n",x,left,right,up,down);    if ((left==inf)&&(right==-inf)&&(up==-inf)&&(down==inf)) return 1;    if ((MAX.x-MIN.x<=x)&&(MAX.y-MIN.y<=x)) return 1; else return 0;} bool judge(int x) {    for (int i=1;i<=4;i++)         for (int j=1;j<=4;j++) if (i!=j) if (work(i,j,x)) return 1;    return 0;} int main() {    scanf("%d",&n);    for (int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);    //printf("%d\n",work(1,2,1)); return 0;    int l=1,r=1e9,ans=0;    while (l<=r) {        //printf("%d %d\n",l,r);        int mid=l+r>>1;        if (judge(mid)) ans=mid,r=mid-1; else l=mid+1;    }    printf("%d\n",ans);    return 0;}