题目大意：给定平面上的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;
}