問題文
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