Darts --HOJ 11960

时间：2010-10-20 来源：勇泽

2、解题思路：（1）由于距离公式定义为：|x1-x2|+|y1-y2|，所以可以将x 、y 分开求解；（2）排序x 、y 分析第 i 个数值的前后关系有 ans+=sum-(n-i)*X[i-1]。

3、注意事项：注意记录sum时，sum越界，需用 double 记录。

4、实现方法:

#include<iostream>
#include<algorithm>
using namespace std;
#define LL double

LL X[10010],Y[10010];
LL sumx,sumy;
int n;

void Solve(int ca)
{
    int i;
    LL ansx=0,ansy=0;
    sumx-=X[0];
    sumy-=Y[0];
    for(i=1;i<n;i++)
    {
        ansx+=sumx-(n-i)*X[i-1];
        sumx-=X[i];
        ansy+=sumy-(n-i)*Y[i-1];
        sumy-=Y[i];
    }
    printf("Case #%d: %I64d\n",ca,(__int64)(ansx+ansy));
}

int main()
{
    int i,T,ca=1;
    cin>>T;
    while(T--)
    {
        sumx=sumy=0;
        cin>>n;
        for(i=0;i<n;i++)
        {
            scanf("%lf%lf",&X[i],&Y[i]);
            sumx+=X[i];
            sumy+=Y[i];
        }
        sort(X,X+n);
        sort(Y,Y+n);
        Solve(ca++);
    }
    return 0;
}