1 //二分判定 覆盖问题 BZOJ 1052 2 // 首先确定一个最小矩阵包围所有点，则最优正方形的一个角一定与矩形一个角重合。 3 // 然后枚举每个角，再解决子问题 4  5 #include <bits/stdc++.h> 6 using namespace std; 7 #define LL long long 8 typedef pair<int,int> pii; 9 const int inf = 1e9;10 const int MOD =5010;11 const int N =5010;12 #define clc(a,b) memset(a,b,sizeof(a))13 const double eps = 1e-8;14 void fre() {freopen("in.txt","r",stdin);}15 void freout() {freopen("out.txt","w",stdout);}16 inline int read() {int x=0,f=1;char ch=getchar();while(ch>‘9‘||ch<‘0‘) {if(ch==‘-‘) f=-1; ch=getchar();}while(ch>=‘0‘&&ch<=‘9‘) {x=x*10+ch-‘0‘;ch=getchar();}return x*f;}17   18 struct node{19     int x[20010],y[20010];20     int num;21 }a,b;22 int n,mid;23   24 void solve2(node &a,int x1,int y1,int x2,int y2){25     int cnt=0;26     for(int i=0;i<a.num;i++){27         if(a.x[i]<x1||a.x[i]>x2||a.y[i]>y2||a.y[i]<y1){28             a.x[cnt]=a.x[i];29             a.y[cnt]=a.y[i];30             cnt++;31         }32     }33     a.num=cnt;34 }35 void solve(node &a,int f){36     int x1=inf,x2=-inf,y1=inf,y2=-inf;37     for(int i=0;i<a.num;i++){38         x1=min(x1,a.x[i]);39         x2=max(x2,a.x[i]);40         y1=min(y1,a.y[i]);41         y2=max(y2,a.y[i]);42     }43     if(f==1) solve2(a,x1,y1,x1+mid,y1+mid);44     if(f==2) solve2(a,x2-mid,y1,x2,y1+mid);45     if(f==3) solve2(a,x1,y2-mid,x1+mid,y2);46     if(f==4) solve2(a,x2-mid,y2-mid,x2,y2);47 }48 bool check(){49     for(int s=1;s<=4;s++){50         for(int t=1;t<=4;t++){51             b.num=a.num;52             for(int i=0;i<b.num;i++){53                 b.x[i]=a.x[i],b.y[i]=a.y[i];54             }55             solve(b,s),solve(b,t);56             int x1=inf,x2=-inf,y1=inf,y2=-inf;57             for(int i=0;i<b.num;i++){58                 x1=min(x1,b.x[i]);59                 x2=max(x2,b.x[i]);60                 y1=min(y1,b.y[i]);61                 y2=max(y2,b.y[i]);62             }63             if(x2-x1<=mid&&y2-y1<=mid) return true;64         }65     } 66     return false;67 }68 int main(){69     n=read();70     for(int i=0;i<n;i++) a.x[i]=read(),a.y[i]=read();71     a.num=n;72     int l=0,r=inf;73     while(l<=r){74         mid=(l+r)>>1;75         if(check()) r=mid-1;76         else l=mid+1;77     }78     printf("%d\n",l);79     return 0;80 }