在平面两点的距离中，曼哈顿距离其实是最容易处理的。
f(A,B)=abs(X(A)-X(B))+abs(Y(A)-Y(B))
之所以说容易处理，是因为X坐标和Y坐标是独立的，
也就是可以把问题划分为两个一维子问题：
一个关于X轴，一个关于Y轴。
对于题目中描述的这种乱七八糟的距离，一个思路就是把x和y剥离出来，分别处理。

对于两个点(a,b) (c,d)在题目中的“距离”
Max(Abs(a-c),Abs(b-d))，可以转化为
(Abs(a+b-c-d)+Abs(a-b-c+d))/2
也就是(a+b,c+d) (a-b,c-d)的曼哈顿距离的一半。
将所有的点(x,y)变换为(x+y,x-y)，然后分别统计每个点在两个维度上的距离和，
也就是分别按X、Y从小到大排序，线性扫描，求和。

关键代码：
        qs(rk,0,N-1,X);
	long long s;
	s=0;
	for (int i=0;i<N;i++){
		if (i)s+=(long long)i*(X[rk[i]]-X[rk[i-1]]);
		dis[rk[i]]+=s;
	}
	s=0;
	for (int i=N-1;i>=0;i--){
		if (i!=N-1)s+=(long long)(N-1-i)*(X[rk[i+1]]-X[rk[i]]);
		dis[rk[i]]+=s;
	}
	qs(rk,0,N-1,Y);
	s=0;
	for (int i=0;i<N;i++){
		if (i)s+=(long long)i*(Y[rk[i]]-Y[rk[i-1]]);
		dis[rk[i]]+=s;
	}
	s=0;
	for (int i=N-1;i>=0;i--){
		if (i!=N-1)s+=(long long)(N-1-i)*(Y[rk[i+1]]-Y[rk[i]]);
		dis[rk[i]]+=s;
	}
	s=dis[0];
	for (int i=0;i<N;i++)if (dis[i]<s)s=dis[i];
	printf("%I64d\n",s>>1);


另：一个思考：如果两点的距离定义为
Min(Abs(x1-x2),Abs(y1-y2))，那么如何处理呢？

• Re:雁过留声——利用曼哈顿距离进行维度分离 (41) liumengyun 2010-02-07 22:26:18
  • 这样计算的话和最大的值结果是一样的。最小值的话不适用这样的性质。 (43) yygy 2012-11-14 19:59:46
• 还是fanhq高明！ (1100) yc5_yc 2012-07-30 13:47:37
• 应该是(a+b,a-b) (c+d,c-d)的曼哈顿距离的一半。 (79) yc5_yc 2012-07-31 13:51:02
• 谢谢楼上的解题报告，记加ID了，WA了一次 (1100) yygy 2012-11-14 19:57:56