1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #define ls(x) a[x].l 6 #define rs(x) a[x].r 7 using namespace std; 8 const int N=500066; 9 int abss(int x){return x<0?-x:x;} 10 int maxn(int a,int b){return a>b?a:b;} 11 int minn(int a,int b){return a<b?a:b;} 12 void swap(int &x,int &y){x^=y;y^=x;x^=y;} 13 14 int cmpid,n,ans; 15 struct son 16 { 17 int x[2]; 18 friend bool operator < (son a,son b) 19 { 20 return a.x[cmpid]>b.x[cmpid]; 21 } 22 }p[N]; 23 24 struct tree 25 { 26 son p; 27 int mx[2],mn[2],l,r; 28 }a[N]; 29 int dis(son a,son b){return abss(a.x[0]-b.x[0])+abss(a.x[1]-b.x[1]);} 30 int maxdis(tree t,son c) 31 { 32 int temp1=maxn( abss(c.x[0]-t.mn[0]),abss(c.x[0]-t.mx[0]) ); 33 int temp2=maxn( abss(c.x[1]-t.mn[1]),abss(c.x[1]-t.mx[1]) ); 34 return temp1+temp2; 35 } 36 int mindis(tree t,son c) 37 { 38 int temp1=maxn(t.mn[0]-c.x[0],0)+maxn(c.x[0]-t.mx[0],0); 39 int temp2=maxn(t.mn[1]-c.x[1],0)+maxn(c.x[1]-t.mx[1],0); 40 return temp1+temp2; 41 } 42 43 struct KDtree 44 { 45 int ans,root,tot,temp; 46 void qqmax(son q,int x,int k) 47 { 48 if(!x)return ; 49 temp=dis(a[x].p,q); 50 if(temp>ans)ans=temp; 51 int l=ls(x),r=rs(x); 52 if(q.x[k]<a[x].p.x[k])swap(l,r);//右边更有可能 53 if(ans<maxdis(a[l],q))qqmax(q,l,k^1); 54 if(ans<maxdis(a[r],q))qqmax(q,r,k^1); 55 } 56 int qqmax(son q) 57 { 58 ans=-0x7fffffff; 59 qqmax(q,root,0); 60 return ans; 61 } 62 void qqmin(son q,int x,int k) 63 { 64 if(!x)return ; 65 temp=dis(a[x].p,q); 66 if(temp<ans&&temp)ans=temp; 67 int l=ls(x),r=rs(x); 68 if(q.x[k]>a[x].p.x[k])swap(l,r);//也是右边更有可能 69 if(mindis(a[l],q)<ans)qqmin(q,l,k^1); 70 if(mindis(a[r],q)<ans)qqmin(q,r,k^1); 71 } 72 int qqmin(son q) 73 { 74 ans=0x7fffffff; 75 qqmin(q,root,0); 76 return ans; 77 } 78 void pushup(int x) 79 { 80 if(!x)return ; 81 if(ls(x)) 82 for(int i=0;i<2;++i) 83 { 84 a[x].mn[i]=minn(a[x].mn[i],a[ls(x)].mn[i]); 85 a[x].mx[i]=maxn(a[x].mx[i],a[ls(x)].mx[i]); 86 } 87 if(rs(x)) 88 for(int i=0;i<2;++i) 89 { 90 a[x].mn[i]=minn(a[x].mn[i],a[rs(x)].mn[i]); 91 a[x].mx[i]=maxn(a[x].mx[i],a[rs(x)].mx[i]); 92 } 93 } 94 void build(int l,int r,int &x,int k) 95 { 96 if(l>r)return ; 97 x=++tot; 98 int mid=(l+r)>>1; 99 cmpid=k; 100 nth_element(p+l,p+mid,p+r+1); 101 a[x].p=p[mid]; 102 for(int i=0;i<2;++i) 103 a[x].mn[i]=a[x].mx[i]=a[x].p.x[i]; 104 build(l,mid-1,ls(x),k^1); 105 build(mid+1,r,rs(x),k^1); 106 pushup(x); 107 } 108 void build() 109 { 110 tot=0; 111 build(1,n,root,0); 112 } 113 }T; 114 int main(){ 115 116 scanf("%d",&n); 117 for(int i=1;i<=n;++i) 118 scanf("%d%d",&p[i].x[0],&p[i].x[1]); 119 120 T.build(); 121 122 ans=0x7fffffff; 123 124 for(int i=1;i<=n;++i) 125 ans=minn(ans,T.qqmax(p[i])-T.qqmin(p[i])); 126 127 cout<<ans; 128 //while(1); 129 return 0; 130 }