题目大意：给定平面上的n个点，求一个点到这n个点的切比雪夫距离之和最小

与3170不同的是这次选择的点无需是n个点中的一个

首先将每一个点(x,y)变为(x+y,x-y) 这样新点之间的曼哈顿距离的一半就是原点之间的切比雪夫距离

因为曼哈顿距离中横纵坐标不互相干扰，因此我们能够将横纵坐标分开处理

每一维要选一个坐标 到其它全部坐标的绝对值之和相等 非常easy想到中位数

可是直接选择中位数得到的点可能横纵坐标奇偶性不同 这样代回原点中发现不是整点

因此假设得到的点横纵坐标奇偶性同样直接输出距离 不同的话选择周围的四个点进行判定 选择最小的距离输出就可以

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define M 100100

using namespace std;

int n,X[M],Y[M];

long long Check(int x,int y)

{

	int i;

	long long re=0;

	for(i=1;i<=n;i++)

		re+=abs(x-X[i])+abs(y-Y[i]);

	return re;

}

int main()

{

	int i,x,y;

	cin>>n;

	for(i=1;i<=n;i++)

	{

		scanf("%d%d",&x,&y);

		X[i]=x+y;Y[i]=x-y;

	}

	sort(X+1,X+n+1);

	sort(Y+1,Y+n+1);

	x=X[n+1>>1];

	y=Y[n+1>>1];

	if( ~(x^y)&1 )

		cout<<Check(x,y)/2<<endl;

	else

		cout<<min(min(Check(x+1,y),Check(x-1,y)),min(Check(x,y+1),Check(x,y-1)))/2<<endl;

	return 0;

}