← 返回题目列表

AtCoder · cf16_exhibition_final_e

E. 供水

中文机器翻译题面 查看原题

分数: 1000 点

问题陈述

有 N 二维平面中的城市。 的坐标 i第城市是 (x_i, y_i)。 最初,水箱中储存的水量 i第城市是 a_i 升。

Snuke可以将任意数量的水从一个城市运送到另一个城市。 然而,当他携带它时,水会漏出一点。 如果他携带 l 升水 s第城到 t第城市,仅 max(l-d_{s,t}, 0) 当他到达目的地时,还剩下多少升水。 这里 d_{s,t} 表示之间的(欧几里德)距离 s第城市和 t第城市。 他可以执行任意数量的此类操作。

Snuke想要最大化最小水量 N 城市。 找到最大值 X 这样他至少可以分发 X 向每个城市提供升水。

约束

  • 1 ≤ N ≤ 15
  • 0 ≤ x_i, y_i, a_i ≤ 10^9
  • 输入中的所有值都是整数。
  • 没有两个城市处于同一位置。

输入

输入由标准输入按以下格式给出:

N
x_1 y_1 a_1
:
x_N y_N a_N

输出

打印最小水量中的最大值 N 城市。 绝对误差或相对误差最多为 10^{-9}.


示例输入 1

3
0 0 10
2 0 5
0 5 8

示例输出 1

6.500000000000

最佳解决方案是携带 3.5 从第一个城市到第二个城市的水升数。 运行后,1号和2号城市都将拥有 6.5 升水,第三个城市将有 8 升水。


示例输入 2

15
335279264 849598327 822889311
446755913 526239859 548830120
181424399 715477619 342858071
625711486 448565595 480845266
647639160 467825612 449656269
160714711 336869678 545923679
61020590 573085537 816372580
626006012 389312924 135599877
547865075 511429216 605997004
561330066 539239436 921749002
650693494 63219754 786119025
849028504 632532642 655702582
285323416 611583586 211428413
990607689 590857173 393671555
560686330 679513171 501983447

示例输出 2

434666178.237122833729