1 #include<cstdio>  2 #include<cstdlib>  3 #include<cmath>  4 #include<cstring>  5 #include<algorithm>  6 #include<iostream>  7 #include<vector>  8 #include<map>  9 #include<set> 10 #include<queue> 11 #include<string> 12 #define inf 1000000000 13 #define maxn 200000+5 14 #define maxm 100000+5 15 #define eps 1e-10 16 #define ll double 17 #define pa pair<ll,int> 18 #define for0(i,n) for(int i=0;i<=(n);i++) 19 #define for1(i,n) for(int i=1;i<=(n);i++) 20 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 21 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 22 #define for4(i,x) for(int i=head[x],y=e[i].go;i;i=e[i].next,y=e[i].go) 23 #define mod 1000000007 24 using namespace std; 25 inline int read() 26 { 27     int x=0,f=1;char ch=getchar(); 28     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 29     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 30     return x*f; 31 } 32 int n,m,cur,ans1,ans2; 33 struct rec 34 { 35     int mi[2],mx[2],d[2],l,r; 36     int& operator [](int i){return d[i];} 37 }p[maxn],t[maxn],now; 38 bool operator <(rec a,rec b){return a[cur]<b[cur];} 39 inline void pushup(int k) 40 { 41     int l=t[k].l,r=t[k].r; 42     for0(i,1) 43     { 44         t[k].mi[i]=min(t[k][i],min(t[l].mi[i],t[r].mi[i])); 45         t[k].mx[i]=max(t[k][i],max(t[l].mx[i],t[r].mx[i])); 46     } 47 } 48 inline int build(int l,int r,int dir) 49 { 50     int mid=(l+r)>>1; 51     cur=dir; 52     nth_element(p+l,p+mid,p+r+1); 53     t[mid]=p[mid]; 54     for0(i,1)t[mid].mi[i]=t[mid].mx[i]=t[mid][i]; 55     t[mid].l=l>mid-1?0:build(l,mid-1,dir^1); 56     t[mid].r=mid+1>r?0:build(mid+1,r,dir^1); 57     pushup(mid); 58     return mid; 59 } 60 inline int dist(rec a,rec b){return abs(a[0]-b[0])+abs(a[1]-b[1]);} 61 inline int calc1(int k) 62 { 63     if(!k)return inf; 64     int ret=0; 65     for0(i,1) 66     { 67         if(now[i]<t[k].mi[i])ret+=t[k].mi[i]-now[i]; 68         if(now[i]>t[k].mx[i])ret+=now[i]-t[k].mx[i]; 69     } 70     return ret; 71 } 72 inline void query1(int k) 73 { 74     if(!k)return; 75     int dl=calc1(t[k].l),dr=calc1(t[k].r),d=dist(t[k],now); 76     if(d&&d<ans1)ans1=d; 77     if(dl<dr) 78     { 79         if(dl<ans1)query1(t[k].l); 80         if(dr<ans1)query1(t[k].r); 81     }else 82     { 83         if(dr<ans1)query1(t[k].r); 84         if(dl<ans1)query1(t[k].l); 85     } 86 } 87 inline int calc2(int k) 88 { 89     if(!k)return -inf; 90     ll ret=0; 91     for0(i,1)ret+=max(abs(t[k].mi[i]-now[i]),abs(t[k].mx[i]-now[i])); 92     return ret; 93 } 94 inline void query2(int k) 95 { 96     if(!k)return; 97     int dl=calc2(t[k].l),dr=calc2(t[k].r),d=dist(t[k],now); 98     if(d>ans2)ans2=d; 99     if(dl>dr)100     {101         if(dl>ans2)query2(t[k].l);102         if(dr>ans2)query2(t[k].r);103     }else104     {105         if(dr>ans2)query2(t[k].r);106         if(dl>ans2)query2(t[k].l);107     }108 }109 int main()110 {111     freopen("input.txt","r",stdin);112     freopen("output.txt","w",stdout);113     n=read();114     for1(i,n)p[i][0]=read(),p[i][1]=read();115     for0(i,1)t[0].mi[i]=inf,t[0].mx[i]=-inf;116     int rt=build(1,n,0),ans=inf;117     for1(i,n)118     {119         now=p[i];120         ans1=inf;ans2=-inf;121         query1(rt);122         query2(rt);123         ans=min(ans,ans2-ans1);124     }125     cout<<ans<<endl;126     return 0;127 }