1688. 接新生

单点时限: 2.0 sec

内存限制: 256 MB

今天正好是新生开学,作为班长的 star, 理所当然的被辅导员委以重任。但是今天有比赛 ,star 不得不在尽量少的时间搞定辅导员安排的任务。
辅导员安排给 star 的任务是,通知每一个新生接待处的同学把新生带到 1 号楼。
这次迎接新生的接待出有 N (N 是不大于 100 的自然数)个点 P1 (X1,Y1)、P2 (X2,Y2)、 …Pn (Xn,Yn),现在要求你帮 star 找一点 P (Xp,Yp),使 P 点到任一点 Pi 的距离 Di 与 Wi 之积之和为最小。

Wi 为到该点的耗费 (star 当然希望耗费最小). 即求 D=W1D1+W2D2+…+WiDi+…+WnDn 有最小值。约定距离 Di=|Xp-Xi|+|Yp-Yi|.Star 今天确实有点忙,所以希望你能帮助他找到这个最小 D 值。

输入格式

数据输入格式是:

  1. 第一行为正整数 N 的值

  2. 第二行至第 N+1 行,每行有三个数,第一和第二个数分别是这个点的 X 与 Y 的坐标,第三个数为它的权重。此三数均为正整数。

输出格式

输出一行分别是 P 点坐标 X 与 Y 和 最小的 D 值。三者之间用空格分隔,末尾不要空格

样例

Input
3
2 4 7
1 2 4
2 3 5
Output
2 3 15

16 人解决,37 人已尝试。

17 份提交通过,共有 120 份提交。

6.6 EMB 奖励。

创建: 12 年,8 月前.

修改: 2 年,9 月前.

最后提交: 7 月,1 周前.

来源: LSP

题目标签