← 返回题目列表

AtCoder · abc401_g

G. 同时推动

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

分数: 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