bzoj 3210: 花神的浇花集会

.

题意：平面上n个点求一点使所有点到它的切比雪夫距离最小。
题解：先把切比雪夫距离转化成曼哈顿距离：把(x,y)变为(x+y,x-y)，新点间的曼哈顿距离的一半就是原点的切比雪夫距离。曼哈顿距离的两维没有联系，所以最小的点的横坐标和纵坐标可以分开求。很明显，要使绝对值的和最小，点肯定在中位数上。但是因为x和y都是整数，x+y和x-y的奇偶性一定相同。中位数求出来的是一奇一偶的话，就在它四周的点找答案。
代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n,x,y;
struct pnt
{
    int x,y;
}p[100010];

int cmp1(pnt x,pnt y)
{
    return x.x<y.x;
}
int cmp2(pnt x,pnt y)
{
    return x.y<y.y;
}
long long get(int x,int y)
{
    long long ans=0;
    for(int i=0;i<n;i++)
    ans+=abs(p[i].x-x)+abs(p[i].y-y);
    return ans;
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        p[i].x=x+y;
        p[i].y=x-y;
    }
    sort(p,p+n,cmp1);
    x=p[n>>1].x;
    sort(p,p+n,cmp2);
    y=p[n>>1].y;
    if((x&1)==(y&1))
    printf("%lld",get(x,y)>>1);
    else
    printf("%lld",min(get(x+1,y),min(get(x-1,y),min(get(x,y+1),get(x,y-1))))>>1);
}