ACM训练联盟周赛 K. Teemo's reunited

Teemo likes to drink raspberry juice. He even spent some of his spare time tomake the raspberry juice himself. The way to make the raspberries juice is simple. You just have to press the raspberries through a fine sieve.

Unfortunately,today Teemo was splited in several pieces by the sieve which was used to makethe raspberry juice. The pieces were losted in the huge two-dimensional map. Onlywhen all the pieces gather, can Teemo drink the raspberry juice he made today.

Teemo's piece can only move parallel to the x or y axis, or he would be hated by theraspberry Queen and will not be able to have raspberry juice any more. One of the piece of Teemo should carry the raspberry juice.In order to avoid spilling, this piece cannot move anymore.

Teemo’spiece are lazy, they’d like to make the sum of paths be the minimal. Your task is to find the minimal sum of the paths.

InputFormat
The first line contains a integer n (1<=n<=100000) represent the number of thepieces. Then next n lines. Each line contains the pairs of xi, yi(-1000000000<xi,yi<1000000000) in turn as points by order.

OutputFormat
Printa single line contains the minimal sum of the paths.

样例输入1

样例输出1

样例输入2

样例输出2

//必须要先排序

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstdlib>

#include <cstring>

#include <string>

#include <deque>

#include <map>

#include <vector>

#include <stack>

using namespace std;

#define  ll long long

#define  N   100009

#define  M 5000000000000009

#define  gep(i,a,b)  for(int  i=a;i<=b;i++)

#define  gepp(i,a,b) for(int  i=a;i>=b;i--)

#define  gep1(i,a,b)  for(ll i=a;i<=b;i++)

#define  gepp1(i,a,b) for(ll i=a;i>=b;i--)

#define  mem(a,b)  memset(a,b,sizeof(a))

#define  ph  push_back

#define  mod  1000000007

struct Node{

    ll id,x,y;

}nod[N];

ll sumx[N],sumy[N],l[N],r[N];

bool cmpx(Node a,Node b){

    return a.x<b.x;

}

bool cmpy(Node a,Node b)

{

    return a.y<b.y;

}

ll n;

int main()

{

    scanf("%lld",&n);

    gep1(i,,n) {

        scanf("%lld%lld",&nod[i].x,&nod[i].y);

        nod[i].id=i;

    }

    sort(nod+,nod++n,cmpx);

    gep(i,,n){

        sumx[i]=sumx[i-]+nod[i].x;

    }

    ll sx=;

    // 1 2 3 4 5 (x)

    // 3   3-1+3-2 +   4-3+5-3

    gep(i,,n){

        sx=nod[i].x*(i-)-sumx[i-]+sumx[n]-sumx[i]-nod[i].x*(n-i);

        l[nod[i].id]=sx;

    }

    sort(nod+,nod++n,cmpy);

    gep(i,,n){

        sumy[i]=sumy[i-]+nod[i].y;

    }

    ll sy=;

    gep(i,,n){

        sy=nod[i].y*(i-)-sumy[i-]+sumy[n]-sumy[i]-nod[i].y*(n-i);

        r[nod[i].id]=sy;//每一次的排序都会造成id的变化，id :最初那个数据在当前的位置

    }

    ll MIN=M;

    gep(i,,n){

        MIN=min(MIN,l[i]+r[i]);

    }

    printf("%lld\n",MIN);

    return ;

}

巴特西

ACM训练联盟周赛 K. Teemo's reunited

样例输入1

样例输出1

样例输入2

样例输出2

最新文章

热门文章