pro： 有N个小松鼠，它们的家用一个点x,y表示，两个点的距离定义为：点(x,y)和它周围的8个点即上下左右四个点和对角的四个点，距离为1。现在N个松鼠要走到一个松鼠家去，求走过的最短距离。0<=N<=10^5 ，-10^9<=x,y<=10^9
sol： 常识告诉我们，8个反向距离相同，等价于切比雪夫距离。 为了方便统计距离，转化为曼哈顿距离。 此题是找一只松鼠家作为中心点，所以不是分别求中位数。
而是枚举每个松鼠，快速计算其他松鼠到他的距离，而快速统计只需要分类正负即可。
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
int x[maxn],y[maxn];ll sum[maxn],ans;
ll sumx[maxn],sumy[maxn];
struct point{ int x,y;}s[maxn];
bool cmpx(point w,point v){ return w.x<v.x; }
bool cmpy(point w,point v){ return w.y<v.y; }
int main()
{
int N;
scanf("%d",&N);
rep(i,,N){
ll tx,ty;
scanf("%d%d",&tx,&ty);
s[i].x=tx+ty; s[i].y=tx-ty;
}
sort(s+,s+N+,cmpx);
rep(i,,N) x[i]=s[i].x,sumx[i]=sumx[i-]+s[i].x;
sort(s+,s+N+,cmpy);
rep(i,,N) y[i]=s[i].y, sumy[i]=sumy[i-]+s[i].y;
rep(i,,N) {
ll tmp=; int pos;
pos=lower_bound(x+,x+N+,s[i].x)-x;
tmp+=1LL*(pos-)*s[i].x-sumx[pos-]+(sumx[N]-sumx[pos-])-1LL*(N-pos+)*s[i].x;
pos=lower_bound(y+,y+N+,s[i].y)-y;
tmp+=1LL*(pos-)*s[i].y-sumy[pos-]+(sumy[N]-sumy[pos-])-1LL*(N-pos+)*s[i].y;
if(i==) ans=tmp;
else ans=min(ans,tmp);
}
cout<<ans/<<endl;
return ;
}