BZOJ 3170 [Tjoi 2013]松鼠聚會

題目描述

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

輸入

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

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

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

輸出

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

樣例輸入

6

-4 -1

-1 -2

2 -4

0 2

0 3

5 -2

樣例輸出

20

解題思路

　　新學了一個姿勢——切比雪夫距離(題目中定義的那個距離)。

　　A(x1,y1)與B(x2,y2)的切比雪夫距離等于A’(x1+y1,x1-y1)和B’(x2+y2,x2-y2)的曼哈頓距離。證明挺簡單的。

　　把每個點$(x,y)$轉換成$(x+y,x-y)$，然後枚舉松鼠們的目的地，找出最短距離。枚舉目的地統計答案用字首和優化。

源代碼

來自于http://blog.csdn.net/aarongzk/article/details/51138617

#include<iostream>  
#include<cstdio>  
#include<cstdlib>  
#include<cstring>  
#include<cmath>  
#include<algorithm>  
#define F(i,j,n) for(int i=j;i<=n;i++)  
#define D(i,j,n) for(int i=j;i>=n;i--)  
#define ll long long  
#define maxn 100005  
#define inf 1000000000000000000ll  
using namespace std;  
int n,pos,x[maxn],y[maxn];  
ll ans,tmp,sumx[maxn],sumy[maxn];  
struct data{ll x,y;}a[maxn];  
inline int read()  
{  
    int x=0,f=1;char ch=getchar();  
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}  
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}  
    return x*f;  
}  
int main()  
{  
    n=read();  
    F(i,1,n)  
    {  
        int xx=read(),yy=read();  
        x[i]=a[i].x=xx+yy;  
        y[i]=a[i].y=xx-yy;  
    }  
    sort(x+1,x+n+1);sort(y+1,y+n+1);  
    F(i,1,n) sumx[i]=sumx[i-1]+x[i],sumy[i]=sumy[i-1]+y[i];  
    ans=inf;  
    F(i,1,n)  
    {  
        pos=lower_bound(x+1,x+n+1,a[i].x)-x;  
        tmp=sumx[n]-sumx[pos]-a[i].x*(n-pos)+a[i].x*pos-sumx[pos];  
        pos=lower_bound(y+1,y+n+1,a[i].y)-y;  
        tmp+=sumy[n]-sumy[pos]-a[i].y*(n-pos)+a[i].y*pos-sumy[pos];  
        ans=min(ans,tmp);  
    }  
    printf("%lld\n",ans/2);  
    return 0;  
}