← 返回题目列表

AtCoder · arc049_b

B. 规范高桥

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

問題文

Norm Takahashi 的可能性是无限的。这个世界上有很多人叫Norm Takahashi。

2 在维度平面上 N 有一个人叫Norm Takahashi。i(1≦i≦N) Norm Takahashi的坐标 我在 (x_i,y_i) 。 每个高桥范数都有一个正整数常数 c_i 被分配并且i 眼睛里有一个点,Norm Takahashi。 移至 (X,Y) 为了搬到 c_i*最大 需要(\|x_i-X|,\|y_i-Y\|) 时间。

你的任务是找出所有高桥诺姆君聚集到某一点所需的最短时间。 这里,在某一点集合所需的最短时间是最晚到达该点的高桥所花费的时间。

Norm Takahashi 将同时开始移动,彼此不会干扰。


入力

输入将以以下格式从标准输入提供。

N
x_1 y_1 c_1
x_2 y_2 c_2
:
x_N y_N c_N
  • 1 第1行有一个整数,代表Norm Takahashi的数量。 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) 用空格分隔。
  • 同一坐标处可能有多个Norm Takahashi。 如果正确答案是满足

部分点

针对此问题设置了部分分数。

  • 任何 关于 i(1≦i≦N) ,c_i=1 的数据集,30 点。 如果您正确回答
  • 如果对于没有附加约束的数据集,除了上述之外,答案是正确的, 70 点。 如果您正确回答

出力

输出所有Norm Takahashi聚集到一点所需的最短时间。 绝对误差或相对误差 10^{−4} 如果答案如下,则正确。在输出末尾添加换行符。


入力例 1

2
0 0 1
10 10 1

出力例 1

5.000000000000000

集合位置 (5,5) 允许两名玩家在 5 秒内移动到该点,这是最短时间。


入力例 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