题目描述

二次元平面上に $N$ 個の都市があります。 $i$ 番目の都市の座標は $(x_i,\ y_i)$ です。 最初に、$i$ 番目の都市にある水の量は $a_i$ リットルです。

すぬけ君は、好きな量の水をある都市から他の都市に運ぶことができます。 しかし、水を運んでいる間に水が少し漏れます。 $s$ 番目の都市から $t$ 番目の都市に $l$ リットルの水を運ぶと、目的地に着いたときに残っている水の量は $max(l-d_{s,t},\ 0)$ だけです。 ここで、$d_{s,t}$ は $s$ 番目の都市と $t$ 番目の都市のユークリッド距離を表します。 すぬけ君は、このタイプの操作を任意の回数繰り返すことができます。

すぬけ君は、$N$ 個の都市にある水の量の最小値を最大化したいです。 全ての都市に少なくとも $X$ リットルの水を配ることができるような最大の $X$ を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $x_1$ $y_1$ $a_1$ : $x_N$ $y_N$ $a_N$

输出格式

$N$ 個の都市にある水の量の最小値を最大値を出力せよ。 絶対誤差または相対誤差が $10^{-9}$ 以下で無ければならない。

题目大意

题目描述

在一个二维平面上有$N$个城市， 第$i$个城市的坐标是$(x_i,y_i)$， 一开始拥有的水量是$a_i$。

现在你可以从一个城市向另一个城市运送任意数量的水， 但水在运输过程中会有损耗， 具体而言如果从$x$城市运$l$水到$y$城市，最终$y$城市得到的水量是$max(0,l-dis(x,y))$， 其中$dis(x,y)$指$x$和$y$城市间的欧几里得距离。 你可以多次进行这个操作。

你要使最终水量最少的城市水量尽量多， 求这个值。

输入输出格式

输入格式

第一行一个正整数$N$。 以下$N$行， 每行三个整数$x_i,y_i,a_i$， 含义如上。

输出格式

一行一个实数$ans$表示最终水量最少的城市水量最多有多少。

3
0 0 10
2 0 5
0 5 8

6.500000000000

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

434666178.237122833729

提示

制約

• $1\ <\ =\ N\ <\ =\ 15$
• $0\ <\ =\ x_i,\ y_i,\ a_i\ <\ =\ 10^9$
• 入力される全ての値は整数である。
• どの二つの都市も同じ場所に無い。

Sample Explanation 1

最適解は、一番目の都市から二番目の都市に $3.5$ リットルの水を運ぶことです。 操作の後、一番目と二番目の都市の水の量はどちらも $6.5$ リットルとなり、三番目の都市の水の量は $8$ リットルとなります。