BZOJ-3170: [Tjoi 2013]松鼠聚会（曼哈顿距离

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3170

首先，修改坐标为(x+y,x-y)，然后转为曼哈顿距离（具体我也不会证明QaQ，还是ORZ网上诸神吧。。。）。

接下来就好求了，对于每个点到其他所有点的曼哈顿距离和可以O（1）求出（分类讨论，分坐标小于该点和大于该点的两部分，前缀和维护一下）。

代码：

3b87e950352ac65cf783247cf9f2b21193138a3f.jpg.png

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
 
using namespace std;
 
#define MAXN 100010
#define inf 0x7fffffff
 
int n,rankx[MAXN],ranky[MAXN];
long long x[MAXN],y[MAXN],N,sumx[MAXN],sumy[MAXN],Min=inf;
 
struct saver {
    long long v;
    int t;
} bx[MAXN],by[MAXN];
 
bool cmp(saver a,saver b) {
    return a.v<b.v;
}
 
int main() {
    scanf("%d",&n);
    for (int i=0;i++<n;) {
        long long X,Y;
        scanf("%lld%lld",&X,&Y);
        x[i]=X+Y,y[i]=X-Y;
        bx[i].v=x[i],by[i].v=y[i],bx[i].t=by[i].t=i;
    }
    sort(bx+1,bx+n+1,cmp),sort(by+1,by+n+1,cmp);
    for (int i=0;i++<n;) {
        if (i==1||bx[i].v!=bx[i-1].v) N=i;
        rankx[bx[i].t]=N;
    }
    for (int i=0;i++<n;) {
        if (i==1||by[i].v!=by[i-1].v) N=i;
        ranky[by[i].t]=N;
    }
    sumx[0]=sumy[0]=0;
    for (int i=0;i++<n;) sumx[i]=sumx[i-1]+bx[i].v,sumy[i]=sumy[i-1]+by[i].v;
    Min*=inf;
    for (int i=0;i++<n;) {
        long long ret=sumx[n]-sumx[rankx[i]]-x[i]*(n-rankx[i]);
        ret+=(x[i]*(rankx[i]-1)-sumx[rankx[i]-1]);
        ret+=(sumy[n]-sumy[ranky[i]]-y[i]*(n-ranky[i]));
        ret+=(y[i]*(ranky[i]-1)-sumy[ranky[i]-1]);
        Min=min(Min,ret);
    }
    printf("%lld\n",Min>>1);
    return 0;
}