ECNUOJ 2616 游黄山

游黄山

Time Limit:1000MS Memory Limit:65536KB
Total Submit:165 Accepted:52 Special Judge

Description

Pollux最近到黄山游玩，他需要在黄山上找一个住宿的地方，Pollux很懒，所以他喜欢住在尽量靠近景点的地方，这样他就可以少走一些路.
现在一张黄山地图上有N个景点，P1（X1，Y1）、P2（X2，Y2）、 …Pn（Xn，Yn）Pollux对每个景点都有一个喜爱值W1，W2，…，Wi，Wn，如果Pollux住在P（X，Y），他到景点Pi的距离Di=|Xp-Xi|+|Yp-Yi|.Pollux希望你能帮他找到
一点P（X，Y），使得D=W1*D1+W2*D2+…+Wi*Di+…+Wn*Dn 有最小值. Pollux很强，可以住在任何地方

Input

第一行为一个整数T,表示测数数据的组数.
每组数据的第一行为正整数N（1<=N<=100）
第二行至第N+1行，每行有三个数，第一和第二个数分别是这个点的X与Y的坐标Pi(xi,yi)，第三个数为Pollux对这个景点的喜爱值Wi.（xi , yi, wi均为浮点小数，且wi为正数）

Output

每组测试数据输出三个数独占一行,分别是P点坐标 X 与 Y 和最小的D值.
可能存在多个满足条件的P点，你只需要输出任意一个即可
三者之间用空格分隔，末尾不要空格，D值相对误差不能超过0.01

Sample Input

3
1
63.34 184.67 0.41
2
0.00 0.00 1.00
10.00 0.00 1.00
3
281.45 57.05 244.64
99.61 168.27 232.81
119.42 29.95 4.91

Sample Output

63.340000 184.670000 0.000000
7.000000 0.000000 10.000000
281.450000 57.050000 69155.926900

Source

华东师范大学2009校赛

解题：一道带权中位数题目

 #include <bits/stdc++.h>

 using namespace std;

 struct Point {

     double x,y,w;

 } p[];

 double sum[];

 bool cmpx(const Point &a,const Point &b) {

     return a.x < b.x;

 }

 bool cmpy(const Point &a,const Point &b) {

     return a.y < b.y;

 }

 int main() {

     int kase,n;

     scanf("%d",&kase);

     while(kase--) {

         scanf("%d",&n);

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

             scanf("%lf %lf %lf",&p[i].x,&p[i].y,&p[i].w);

         sort(p,p+n,cmpx);

         sum[] = p[].w;

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

             sum[i] = p[i].w + sum[i-];

         double total = sum[n-],x,y;

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

             double left = i?sum[i-]:;

             double right = sum[n-] - sum[i];

             if(left <= 0.5*total && right <= 0.5*total) {

                 x = p[i].x;

                 break;

             }

         }

         sort(p,p+n,cmpy);

         sum[] = p[].w;

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

             sum[i] = sum[i-] + p[i].w;

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

             double left = i?sum[i-]:;

             double right = sum[n-] - sum[i];

             if(left <= 0.5*total && right <= 0.5*total) {

                 y = p[i].y;

                 break;

             }

         }

         double ret = ;

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

             ret += p[i].w*(fabs(p[i].x - x) + fabs(p[i].y - y));

         printf("%.6f %.6f %.6f\n",x,y,ret);

     }

     return ;

 }

巴特西

ECNUOJ 2616 游黄山

最新文章

热门文章