3170: [Tjoi 2013]松鼠聚会

Time Limit: 1 Sec

Memory Limit: 256 MB

题目连接

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

Description

Input

//qscqesze

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <bitset>

#include <vector>

#include <sstream>

#include <queue>

#include <typeinfo>

#include <fstream>

#include <map>

#include <stack>

typedef long long ll;

using namespace std;

//freopen("D.in","r",stdin);

//freopen("D.out","w",stdout);

#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)

#define maxn 100010

#define eps 1e-9

int Num;

//const int inf=0x7fffffff;   //§&szlig;§é§à§é¨f§3

const int inf=0x3f3f3f3f;

inline ll read()

{

    ll x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

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

struct node

{

    double x,y;

    int id;

}p[maxn];

double ans[maxn];

bool cmp1(node a,node b)

{

    return a.x<b.x;

}

bool cmp2(node a,node b)

{

    return a.y<b.y;

}

int main()

{

    int n=read();

    double sumx=,sumy=;

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

    {

        double x,y;

        scanf("%lf%lf",&x,&y);

        p[i].x = (x+y)/;

        p[i].y = (x-y)/;

        sumx += p[i].x;

        sumy += p[i].y;

        p[i].id = i;

    }

    sort(p,p+n,cmp1);

    double tmp=;

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

    {

        ans[p[i].id]+=(i)*p[i].x - tmp;

        ans[p[i].id]+=(sumx-tmp)-(n-i)*p[i].x;

        tmp+=p[i].x;

    }

    sort(p,p+n,cmp2);

    tmp=;

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

    {

        ans[p[i].id]+=(i)*p[i].y - tmp;

        ans[p[i].id]+=(sumy-tmp)-(n-i)*p[i].y;

        tmp+=p[i].y;

    }

    double Ans = ans[];

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

        Ans = min(Ans,ans[i]);

    printf("%.0lf\n",Ans);

}