Eva

Time Limit: 10 Sec  Memory Limit: 128 MB
Description

有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

/**************************************************************

    Problem: 3170

    User: ictsing

    Language: C++

    Result: Accepted

    Time:504 ms

    Memory:5980 kb

****************************************************************/

 

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

const int mt=1e5+7;

typedef long long ll;

struct node

{

    ll x,y;

 

}nd[mt];

inline int read()

{

    int num=0,flag=1;

    char ch;

    do{

        ch=getchar();

        if(ch=='-') flag=-1;

    }while(ch<'0'||ch>'9');

    do{

        num=num*10+ch-'0';

        ch=getchar();

    }while(ch>='0'&&ch<='9');

    return num*flag;

}

ll X[mt],Y[mt],sumX[mt],sumY[mt];

int main()

{

    int n=read(),a,b;

    for(int i=1;i<=n;i++)

        a=read(),b=read(),nd[i].x=X[i]=a+b,nd[i].y=Y[i]=a-b;

    sort(X+1,X+n+1),sort(Y+1,Y+n+1);

    for(int i=1;i<=n;i++)

    sumX[i]=sumX[i-1]+X[i],sumY[i]=sumY[i-1]+Y[i];

    ll ans=1ll<<62,tmp;

    int pos;

    for(int i=1;i<=n;i++)

    {

        tmp=0;

        pos=lower_bound(X+1,X+n+1,nd[i].x)-X;

        tmp+=(nd[i].x*pos-sumX[pos])+(sumX[n]-sumX[pos]-(n-pos)*nd[i].x);

        pos=lower_bound(Y+1,Y+n+1,nd[i].y)-Y;

        tmp+=(nd[i].y*pos-sumY[pos])+(sumY[n]-sumY[pos]-(n-pos)*nd[i].y);

        ans=min(ans,tmp);

    }

    printf("%lld\n",ans/2);

    return 0;

}