(x1 , y1)到(x2 , y2)的曼哈顿距离 |x1-x2| + |y1-y2|,切比雪夫距离 max（ |x1 - x2| ，|y1 - y2|）

将原坐标系中的点 ( x , y ) 转化为( x+y , x-y ) ，则新坐标系中的切比雪夫距离等于原坐标系中的曼哈顿距离
如果转化为（ (x+y)/2 , (x-y)/2 ），则新坐标系中的曼哈顿距离等于原坐标系中的切比雪夫距离 ，在第二类转化中为了防止出现小数影响结果，可以先*2，最后结果除以2即可

P5098 [USACO04OPEN]Cave Cows 3 洞穴里的牛之三(洛谷)

分析 : 第一类转化后求最小的切比雪夫距离吗，求出横纵坐标的最大最小值即可
code : 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	int n,a,b,maxx=0,maxy=0,minx=1e7,miny=1e7;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {
		scanf("%d%d",&a,&b);
		maxx=max(maxx,a+b);
		minx=min(minx,a+b);
		maxy=max(maxy,a-b);
		miny=min(miny,a-b);
	}
	printf("%d",max(maxx-minx,maxy-miny));
	return 0;	
} 

P3964 [TJOI2013]松鼠聚会(洛谷) / BZOJ3170

分析 ：第二类转化坐标后，问题转化为确定某一点使其他点到该点的曼哈顿距离和最小，输出最小距离和。对点 i 和 j ，j 对 i 在横坐标上的的贡献是  | xj - xi | ，设前k个点横坐标<= xi ,假设最后确定的终点为 i，所有点横坐标的贡献和为
对于和，可以预处理出前缀和，然后按x坐标排序后可以二分得到k，对纵坐标的贡献求法同理可得
code : 抽时间补