AT_abc401_g.[ABC401G] Push Simultaneously

平面上有 $N$ 个高桥君和 $N$ 个按钮。平面上设有原点，从原点向东移动 $x$ 米、向北移动 $y$ 米的位置用坐标 $(x,y)$ 表示。第 $i$ 个高桥君 $(1 \leq i \leq N)$ 初始位于坐标 $(\mathit{sx}_i, \mathit{sy}_i)$，第 $i$ 个按钮位于坐标 $(\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'$ $(t' > t)$，存在整数 $i$ $(1 \leq i \leq N)$ 使得 $(x_i(t'), y_i(t')) = (\mathit{gx}_j, \mathit{gy}_j)$ 成立。

输入通过标准输入给出，格式如下：

$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 \leq N \leq 300$
• $0 \leq \mathit{sx}_i \leq 10^{18}$ $(1 \leq i \leq N)$
• $0 \leq \mathit{sy}_i \leq 10^{18}$ $(1 \leq i \leq N)$
• $0 \leq \mathit{gx}_i \leq 10^{18}$ $(1 \leq i \leq N)$
• $0 \leq \mathit{gy}_i \leq 10^{18}$ $(1 \leq i \leq N)$
• $(\mathit{sx}_i, \mathit{sy}_i) \neq (\mathit{sx}_j, \mathit{sy}_j)$ $(1 \leq i < j \leq N)$
• $(\mathit{gx}_i, \mathit{gy}_i) \neq (\mathit{gx}_j, \mathit{gy}_j)$ $(1 \leq i < 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)$
• 输入的所有数值均为整数

样例解释 1

初始时，高桥君和按钮的位置关系如图所示。

假设第 $1,2,3,4$ 个高桥君分别直接向第 $1,3,2,4$ 个按钮移动。

这样，高桥君们分别在开始后 $2$ 秒、$\sqrt{2}$ 秒、$1$ 秒、$\sqrt{2}$ 秒时到达对应按钮的坐标。因此，可以在开始后 $2$ 秒时同时按下所有按钮。反之，无法在 $2$ 秒之前同时按下所有按钮，所以输出 2。只要输出值与真实值的相对误差不超过 $10^{-6}$，例如 1.999998 或 2.00000014 也会被判定为正确。

样例解释 2

注意输入的坐标可能超出 $32$ 位整数的范围。

翻译由 DeepSeek V3 完成