2136: 统帅三军!

Submit Page Summary Time Limit: 1 Sec Memory Limit: 128 Mb Submitted: 55 Solved: 11

Description

Wells最近迷上了一款攻城的策略游戏，点就去就能当大元帅统帅三军！

游戏界面主要是一个平面(坐标可以为浮点数)，然而Wells发现这游戏是个骗局，其实只给了一个军队。

Wells初始有一个军队，仅包含n个士兵，每个士兵有一个初始位置（x,y）和一个劳累指数Wi，每个队员可以移动，显然对于每个队员的移动是需要消耗一些体力的，若第i个队员从位置（x1,y1）移动到（x2,y2）的体力消耗为Wi*(|x2-x1|+|y2-y1|)。

Wells希望先将队伍集合起来，且希望整个队伍一次集合的体力消耗越少越好。显然能量消耗的多少直接取决与Wells对于会和点（x,y）的选择，然而Wells太懒了，希望你帮他找出某个时刻的最佳会和点。

Input

对于每组数据：

第一行：一个整数N，表示士兵数目。

第二行：一共N个整数，其中的第i个数Wi表示第i个队员的劳累指数。(N<=106)(N<=106)

接下来N行：每一行两个整数X和Y，表示第i个士兵的当前的横坐标和纵坐标。(−109<=X,Y<=109)(−109<=X,Y<=109)

Output

一个实数。表示所有队员集合到最佳攻击位置的体力消耗总和，答案保留两位小数。

Sample Input

Sample Output

0.00

Hint

Source

Author

Wells

题意：带权中位数

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

const int maxn =1e6+;

struct data {

    int x,y,w;

};

data num[maxn];

int n,i,j,k;

double sum,ans,xx,yy;

int xl,yl;

int cmp(data a,data b) {

    return a.x<b.x;

}

int cmp1(data a,data b) {

    return a.y<b.y;

}

int main() {

    int T;

    ios::sync_with_stdio(false);

    cin.tie();

        cin>>n;

        sum=ans=xx=yy=;

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

            cin>>num[i].w;

            sum+=num[i].w;

        }

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

            cin>>num[i].x>>num[i].y;

        sort(num+,num+n+,cmp);

        double mid=sum/;

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

            xx+=num[i].w;

            if (xx>=mid) {

                xl=num[i].x;

                break;

            }

        }

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

            ans+=num[i].w*(abs(num[i].x-xl));

        sort(num+,num+n+,cmp1);

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

            yy+=num[i].w;

            if (yy>=mid) {

                yl=num[i].y;

                break;

            }

        }

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

            ans+=num[i].w*(abs(num[i].y-yl));

        printf("%0.2lf\n",ans);

    return ;

}