小猪iPig在PKU刚上完了无聊的猪性代数课，天资聪慧的iPig被这门对他来说无比简单的课弄得非常寂寞，为了消除寂寞感，他决定和他的好朋友giPi（鸡皮）玩一个更加寂寞的游戏---捉迷藏。 但是，他们觉得，玩普通的捉迷藏没什么意思，还是不够寂寞，于是，他们决定玩寂寞无比的螃蟹版捉迷藏，顾名思义，就是说他们在玩游戏的时候只能沿水平或垂直方向走。一番寂寞的剪刀石头布后，他们决定iPig去捉giPi。由于他们都很熟悉PKU的地形了，所以giPi只会躲在PKU内n个隐秘地点，显然iPig也只会在那n个地点内找giPi。游戏一开始，他们选定一个地点，iPig保持不动，然后giPi用30秒的时间逃离现场（显然，giPi不会呆在原地）。然后iPig会随机地去找giPi，直到找到为止。由于iPig很懒，所以他到总是走最短的路径，而且，他选择起始点不是随便选的，他想找一个地点，使得该地点到最远的地点和最近的地点的距离差最小。iPig现在想知道这个距离差最小是多少。 由于iPig现在手上没有电脑，所以不能编程解决这个如此简单的问题，所以他马上打了个电话，要求你帮他解决这个问题。iPig告诉了你PKU的n个隐秘地点的坐标，请你编程求出iPig的问题。

第一行输入一个整数N 第2~N+1行，每行两个整数X，Y，表示第i个地点的坐标

一个整数，为距离差的最小值。

对于30%的数据,N<=1000 对于100%的数据，N<=500000,0<=X,Y<=10^8 保证数据没有重点保证N>=2

  1 //It is made by wfj_2048~  2 #include <algorithm>  3 #include <iostream>  4 #include <cstring>  5 #include <cstdlib>  6 #include <cstdio>  7 #include <vector>  8 #include <cmath>  9 #include <queue> 10 #include <stack> 11 #include <map> 12 #include <set> 13 #define inf (1<<30) 14 #define N (1000010) 15 #define il inline 16 #define RG register 17 #define ll long long 18 #define min(a,b) (a<b ? a : b) 19 #define max(a,b) (a>b ? a : b) 20 #define abs(x) ((x)>0 ? (x) : -(x)) 21 #define fi01() for (RG int i=0;i<=1;++i) 22 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) 23  24 using namespace std; 25  26 int K,n,rt,ans,ans1,ans2; 27  28 struct node{ 29      30     int a[2],mn[2],mx[2],l,r; 31  32     bool operator < (const node &t) const{ 33     return a[K]<t.a[K]; 34     } 35      36 }t[N],S; 37  38 il int gi(){ 39     RG int x=0,q=1; RG char ch=getchar(); 40     while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar(); 41     if (ch==‘-‘) q=-1,ch=getchar(); 42     while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar(); 43     return q*x; 44 } 45  46 il void merge(RG int x){ 47     fi01(){ 48     if (t[x].l){ 49         t[x].mn[i]=min(t[x].mn[i],t[t[x].l].mn[i]); 50         t[x].mx[i]=max(t[x].mx[i],t[t[x].l].mx[i]); 51     } 52     if (t[x].r){ 53         t[x].mn[i]=min(t[x].mn[i],t[t[x].r].mn[i]); 54         t[x].mx[i]=max(t[x].mx[i],t[t[x].r].mx[i]); 55     } 56     } 57     return; 58 } 59  60 il int build(RG int l,RG int r,RG int p){ 61     K=p; RG int mid=(l+r)>>1; nth_element(t+l,t+mid,t+r+1); 62     fi01() t[mid].mn[i]=t[mid].mx[i]=t[mid].a[i]; 63     if (l<mid) t[mid].l=build(l,mid-1,p^1); 64     if (r>mid) t[mid].r=build(mid+1,r,p^1); 65     merge(mid); return mid; 66 } 67  68 il int get1(RG int x){ 69     if (!x) return inf; RG int res=0; 70     fi01() res+=max(0,t[x].mn[i]-S.a[i])+max(0,S.a[i]-t[x].mx[i]); 71     return res; 72 } 73  74 il int get2(RG int x){ 75     if (!x) return 0; RG int res=0; 76     fi01() res+=max(abs(t[x].mn[i]-S.a[i]),abs(S.a[i]-t[x].mx[i])); 77     return res; 78 } 79  80 il void querymin(RG int x){ 81     RG int res=abs(S.a[0]-t[x].a[0])+abs(S.a[1]-t[x].a[1]); 82     if (res<ans1 && res) ans1=res; 83     RG int dl=get1(t[x].l),dr=get1(t[x].r); 84     if (dl<dr){ 85     if (dl<ans1) querymin(t[x].l); 86     if (dr<ans1) querymin(t[x].r); 87     } else{ 88     if (dr<ans1) querymin(t[x].r); 89     if (dl<ans1) querymin(t[x].l); 90     } 91     return; 92 } 93  94 il void querymax(RG int x){ 95     ans2=max(ans2,abs(S.a[0]-t[x].a[0])+abs(S.a[1]-t[x].a[1])); 96     RG int dl=get2(t[x].l),dr=get2(t[x].r); 97     if (dl>dr){ 98     if (dl>ans2) querymax(t[x].l); 99     if (dr>ans2) querymax(t[x].r);100     } else{101     if (dr>ans2) querymax(t[x].r);102     if (dl>ans2) querymax(t[x].l);103     }104     return;105 }106 107 il void work(){108     n=gi();109     for (RG int i=1;i<=n;++i) t[i].a[0]=gi(),t[i].a[1]=gi();110     rt=build(1,n,0),ans=inf;111     for (RG int i=1;i<=n;++i){112     S=t[i],ans1=inf,ans2=0;113     querymin(rt),querymax(rt);114     ans=min(ans,ans2-ans1);115     }116     printf("%d\n",ans); return;117 }118 119 int main(){120     File("hide");121     work();122     return 0;123 }