分数: 575 点
问题陈述
有 N 人和 N 按钮。平面有原点和坐标 (x, y) 代表的位置是 x 米东和 y 原点以北米。 的 i第一个人 (1 \le i \le N) 开始于 (\mathit{sx}_i,\mathit{sy}_i)。 的 i第一个按钮 (1 \le i \le N) 位于 (\mathit{gx}_i,\mathit{gy}_i).
人们想要移动并按下这些 N 按钮 同时。 按钮只能由与该按钮处于同一坐标的人按下。 到达坐标后按下按钮所需的时间为 0 秒。
每个人最多可以向任意方向移动 1 米每秒。 更正式地说,如果 开始后 i第一个人 t 秒 (x_i(t), y_i(t)),以下所有条件必须成立:
- x_i(0) = \mathit{sx}_i;
- y_i(0) = \mathit{sy}_i;
- 对于所有非负实数 t_0, t_1,之间的距离 (x_i(t_0), y_i(t_0)) 和 (x_i(t_1), y_i(t_1)) 最多是 |t_0 - t_1|.
找出人们实现目标所需的时间。 形式上,找到最小值 t 满足以下条件:
- 可以设置 x_i 和 y_i 在上述条件下,对于每个整数 j\ (1\leq j\leq N) 和每个实数 t ^ \prime\ (t ^ \prime\gt t),存在一个整数 i\ (1\leq i\leq N) 与 (x _ i(t ^ \prime),y _ i(t ^ \prime))=(\mathit{gx} _ j,\mathit{gy} _ j).
约束
- 1\leq N\leq 300
- 0\leq\mathit{sx} _ i\leq10 ^ {18}\ (1\leq i\leq N)
- 0\leq\mathit{sy} _ i\leq10 ^ {18}\ (1\leq i\leq N)
- 0\leq\mathit{gx} _ i\leq10 ^ {18}\ (1\leq i\leq N)
- 0\leq\mathit{gy} _ i\leq10 ^ {18}\ (1\leq i\leq N)
- (\mathit{sx} _ i,\mathit{sy} _ i)\neq(\mathit{sx} _ j,\mathit{sy} _ j)\ (1\leq i\lt j\leq N)
- (\mathit{gx} _ i,\mathit{gy} _ i)\neq(\mathit{gx} _ j,\mathit{gy} _ j)\ (1\leq i\lt j\leq N)
- (\mathit{sx} _ i,\mathit{sy} _ i)\neq(\mathit{gx} _ j,\mathit{gy} _ j)\ (1\leq i\leq N,1\leq j\leq N)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N
\mathit{sx}_1 \mathit{sy}_1
\mathit{sx}_2 \mathit{sy}_2
\vdots
\mathit{sx}_N \mathit{sy}_N
\mathit{gx}_1 \mathit{gy}_1
\mathit{gx}_2 \mathit{gy}_2
\vdots
\mathit{gx}_N \mathit{gy}_N
输出
打印所需时间 N 人来按 同时按下 N 按钮。 如果与真实值的相对误差最多为,则您的输出被认为是正确的 10^{-6}.
示例输入 1
4 0 0 0 1 2 0 3 1 0 2 1 0 1 2 2 2
示例输出 1
2
最初,人物和按钮的位置如下所示。

假设人 1,2,3,4 直接向按钮移动 1,3,2,4。

他们到达各自的按钮后 2, \sqrt2, 1,和 \sqrt2 秒。
因此,可以同时按下所有按钮 开始后 2 秒。
相反,他们不能同时按下所有按钮 2 秒,所以打印 2.
因为如果输出与真实值的相对误差最多为 10^{-6},输出如 1.999998 or 2.00000014 对于该测试用例也被认为是正确的。
示例输入 2
3 1 4 1 5 9 2 653589793238462643 383279502884197169 399375105820974944 592307816406286208 99862803482534211 706798214808651328
示例输出 2
757682516069002110.04581169374262658710741005525
请注意,输入的坐标可能不适合 32位整数。
示例输入 3
12 4459915897 5789359311 4393259463 4247016333 4827828467 4179021045 2654035685 3406423989 1790405301 4886103164 2978675817 4818583236 5912369644 5824121992 6016882384 4165667191 4305949638 3454894060 6545166942 5390976281 4043403253 4019611554 3462096432 4117859301 3528911877 4631601790 4627979431 4814676729 3810130146 5728760563 5586470124 3310360339 3664130072 4525834271 1710246881 3750440871 3143440609 5038869551 2294021341 3965849888 6189106395 4499485672 4799619607 5151972020 6905793542 3976136296 1764267574 4525373194
示例输出 3
1299999319.116399442508650717909981965254