B - 高橋ノルム君 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋ノルム君の可能性は無限大です。高橋ノルムという名前の人物はこの世界にたくさんいます。

2 次元平面上に N 人の高橋ノルム君がいます。i(1≦i≦N) 人目の高橋ノルム君は座標 (x_i,y_i) にいます。 各高橋ノルム君には正整数定数 c_i が割り当てられており、i 人目の高橋ノルム君がある点 (X,Y) に移動するためには c_i*max(\|x_i-X|,\|y_i-Y\|) の時間がかかります。

あなたの仕事は、全ての高橋ノルム君が一点に集まるために必要な最小の時間を求めることです。 ここで、一点に集まるために必要な最小の時間とは最も遅くその点に到着する高橋君の移動にかかった時間とします。

高橋ノルム君は一斉に動き出し、お互いに干渉せず動くものとします。

入力

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

N
x_1 y_1 c_1
x_2 y_2 c_2
:
x_N y_N c_N
  • 1 行目には、高橋ノルム君の数を表す整数 N (2≦N≦1,000) が与えられる。
  • 2 行目からの N 行のうち i (1≦i≦N) 行目には、i 人目の高橋君の二次元平面上の位置と定数を表す 3 つの整数 x_i,y_i,c_i (-10^5≦x_i,y_i≦10^5,1≦c_i≦1,000) が空白区切りで与えられる。
  • 同じ座標に複数の高橋ノルム君がいることもあります。

部分点

この問題には部分点が設定されている。

  • 任意の i(1≦i≦N) について、c_i=1 を満たすデータセットに正解した場合は、30 点が与えられる。
  • 追加制約のないデータセットに正解した場合は、上記とは別に 70 点が与えられる。

出力

全ての高橋ノルム君が一点に集まるために必要な最小の時間を出力せよ。 絶対誤差または相対誤差が 10^{−4} 以下ならば正解となる。 出力の末尾には改行を入れること。

入力例 1

2
0 0 1
10 10 1

出力例 1

5.000000000000000

集合位置を (5,5) にすれば、5秒で2人ともその点に移動することができ、これが最小である。

入力例 2

2
0 0 1
10 10 2

出力例 2

6.666666666666667

入力例 3

10
-27 -67 10
59 13 10
14 -15 9
-29 -84 7
-75 -2 2
-12 -74 5
77 31 9
40 64 8
-81 32 1
81 26 5

出力例 3

582.222222222222222

入力例 4

8
-81739 73917 446
42230 30484 911
79354 -50126 200
33440 -47087 651
-73 84114 905
79222 -53608 713
65194 -46284 685
81145 40933 47

出力例 4

54924095.383189122374461