2616. 游黄山

单点时限: 2.0 sec

内存限制: 256 MB

Pollux 最近到黄山游玩,他需要在黄山上找一个住宿的地方,Pollux 很懒,所以他喜欢住在尽量靠近景点的地方,这样他就可以少走一些路。

现在一张黄山地图上有 $N$ 个景点,$P_1(x_1,y_1), P_2(x_2,y_2), \ldots, P_n(x_n,y_n)$。Pollux 对每个景点都有一个喜爱值 $w_1,w_2,\ldots,w_n$,如果 Pollux 住在 $P(x,y)$,他到景点 $P_i(x_i,y_i)$ 的距离 $d_i=|x-x_i|+|y-y_i|$。Pollux 希望你能帮他找到一点 $P(x,y)$,使得 $D=\sum_{i=1}^N w_i \cdot d_i$ 有最小值。Pollux 很强,可以住在任何地方。

输入格式

第一行为一个整数 $T$,表示测数数据的组数。

每组数据的第一行为 正整数 $N$ ($1 \le N \le 100$)

第二行至第 $N+1$ 行,每行有三个数,第一和第二个数分别是这个点的 $x$ 与 $y$ 的坐标 $P_i(x_i,y_i)$,第三个数为 Pollux 对这个景点的喜爱值 $w_i$.($x_i,y_i,w_i$ 均为浮点小数,且 $w_i$ 为正数)

输出格式

每组测试数据输出三个数独占一行,分别是 $P$ 点坐标 $X$ 与 $Y$ 和 最小的 $D$ 值。

可能存在多个满足条件的 $P$ 点,你只需要输出任意一个即可。

三者之间用空格分隔,末尾不要空格,$D$ 值相对误差不能超过 $0.01$。

样例

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
Output
63.340000 184.670000 0.000000
7.000000 0.000000 10.000000
281.450000 57.050000 69155.926900

53 人解决,70 人已尝试。

82 份提交通过,共有 196 份提交。

3.8 EMB 奖励。

创建: 11 年,2 月前.

修改: 2 年,7 月前.

最后提交: 3 月前.

来源: 华东师范大学2009校赛

题目标签