/ 
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 1000 点
問題文
二次元平面上に 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 を求めてください。
制約
- 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 リットルの水を運ぶことです。 操作の後、一番目と二番目の都市の水の量はどちらも 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
Score : 1000 points
Problem Statement
There are N cities in a two-dimensional plane. The coordinates of the i-th city is (x_i, y_i). Initially, the amount of water stored in the i-th city is a_i liters.
Snuke can carry any amount of water from a city to another city. However, water leaks out a bit while he carries it. If he carries l liters of water from the s-th city to the t-th city, only max(l-d_{s,t}, 0) liters of water remains when he arrives at the destination. Here d_{s,t} denotes the (Euclidean) distance between the s-th city and the t-th city. He can perform arbitrary number of operations of this type.
Snuke wants to maximize the minimum amount of water among the N cities. Find the maximum X such that he can distribute at least X liters of water to each city.
Constraints
- 1 ≤ N ≤ 15
- 0 ≤ x_i, y_i, a_i ≤ 10^9
- All values in the input are integers.
- No two cities are at the same position.
Input
The input is given from Standard Input in the following format:
N x_1 y_1 a_1 : x_N y_N a_N
Output
Print the maximum of the minimum amount of water among the N cities. The absolute error or the relative error must be at most 10^{-9}.
Sample Input 1
3 0 0 10 2 0 5 0 5 8
Sample Output 1
6.500000000000
The optimal solution is to carry 3.5 liters of water from the 1st city to the 2nd city. After the operation, both the 1st and the 2nd cities will have 6.5 liters of water, and the 3rd city will have 8 liters of water.
Sample Input 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
Sample Output 2
434666178.237122833729