AT_abc401_g [ABC401G] Push Simultaneously

[problemUrl]: https://atcoder.jp/contests/abc401/tasks/abc401_g 平面上有 $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 完成