bzoj3170 [Tjoi2013]松鼠聚會 切比雪夫距離

​​http://www.elijahqi.win/archives/3126​​​

Description

有N個小松鼠，它們的家用一個點x,y表示，兩個點的距離定義為：點(x,y)和它周圍的8個點即上下左右四個點和對角的四個點，距離為1。現在N個松鼠要走到一個松鼠家去，求走過的最短距離。

Input

第一行給出數字N，表示有多少隻小松鼠。0<=N<=10^5

下面N行，每行給出x,y表示其家的坐标。

-10^9<=x,y<=10^9

Output

表示為了聚會走的路程和最小為多少。

Sample Input

6

-4 -1

-1 -2

2 -4

0 2

0 3

5 -2

Sample Output

20

HINT

Source

考慮松鼠行進的路線就是切比雪夫距離 但是切比雪夫距離無法快速計算 是以考慮轉化坐标系 将切比雪夫距離等價于曼哈頓距離 就可以預處理字首和字尾和每次o1分開計算答案即可

#include<cstdio>
#include<cctype>
#include<algorithm>
#define ll long long
using namespace std;
inline char gc(){
    static char now[1<<16],*S,*T;
    if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
    return *S++;
}
inline int read(){
    int x=0,f=1;char ch=gc();
    while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();}
    while(isdigit(ch)) x=x*10+ch-'0',ch=gc();
    return x*f;
}
const int N=1e5+10;
struct node{int x,y;}p[N];
inline bool cmp1(const int &a,const int &b){return p[a].x<p[b].x;}
inline bool cmp2(const int &a,const int &b){return p[a].y<p[b].y;}
int n,rk1[N],rk2[N],bl1[N],bl2[N]; 
ll pre[N],pre1[N],suc[N],suc1[N];
int main(){
    freopen("bzoj3170.in","r",stdin);
    n=read();int x,y;
    for (int i=1;i<=n;++i) {
        x=read();y=read();p[i].x=x+y;p[i].y=x-y;
    }ll ans=1LL<<60;
    for (int i=1;i<=n;++i) bl1[i]=bl2[i]=i;
    sort(bl1+1,bl1+1+n,cmp1);sort(bl2+1,bl2+1+n,cmp2);
    for (int i=1;i<=n;++i) pre[i]=pre[i-1]+p[bl1[i]].x;
    for (int i=n;i;--i) suc[i]=suc[i+1]+p[bl1[i]].x;
    for (int i=1;i<=n;++i) pre1[i]=pre1[i-1]+p[bl2[i]].y;
    for (int i=n;i;--i) suc1[i]=suc1[i+1]+p[bl2[i]].y;
    for (int i=1;i<=n;++i) rk1[bl1[i]]=i,rk2[bl2[i]]=i;
    for (int i=1;i<=n;++i){
        static int id;static ll tmpx,tmpy;
        id=rk1[i];tmpx=(ll)id*p[i].x-pre[id]+suc[id+1]-(ll)p[i].x*(n-id);
        id=rk2[i];tmpy=(ll)id*p[i].y-pre1[id]+suc1[id+1]-(ll)p[i].y*(n-id);
        ans=min(ans,tmpx+tmpy);
    }printf("%lld\n",ans>>1);
    return 0;
}