AT_s8pc_6_d.Snowballs

在一条自西向东延伸的较长直线上，放置着 $N$ 个雪球。这里所说的「位置 $X$」，是指从一个参考点出发，沿这条直线向东移动 $X$ 的位置。

第 $i$ 个雪球位于距道路西端 $X_i$ 的位置，半径为 $R_i$。假设所有雪球都是完美的球状。

E869120 君想要通过合并这些雪球，尽可能地做出一个大雪球。

当一个雪球移动距离 $d$ 时，其半径就会减少 $d$。如果半径变为 $0$，该雪球将消失。此外，可以将相同位置的雪球进行合并。具有半径 $r_1$ 和 $r_2$ 的两个雪球合并后，新雪球的半径为 $\left(r_1^3 + r_2^3\right)^{1/3}$。

那么，E869120 君能做出半径最大的雪球是多少呢？

输入以以下格式提供：

$N$ $X_1$ $R_1$ $X_2$ $R_2$ \dots $X_N$ $R_N$

输出 E869120 君能够制成的最大雪球的半径。要求答案的相对误差或绝对误差在 $10^{-4}$ 以内即可视为正确。

限制

• $1 \leq N \leq 100\,000$
• $1 \leq X_i \leq 1\,000\,000\,000$
• $1 \leq R_i \leq 1\,000\,000\,000$

子任务与得分

本题分为若干子任务，只有当提交通过该子任务的所有测试用例时，才视为通过该子任务。最终得分为通过的所有子任务分数之和：

1. (70 分)：$N = 2$
2. (140 分)：$N \leq 15$
3. (250 分)：$N \leq 1\,000$
4. (140 分)：无其它限制

示例解释

示例解释 1

通过以下操作，可以制成半径为 $737^{1/3} = 9.03280...$ 的雪球：

• 将第一个雪球向东移动 $3$ 个单位，其半径减少至 $2$。
• 合并第一个雪球和第二个雪球，合并后的半径为 $\left(9^3 + 2^3\right)^{1/3} = 9.03280...$。
  这就是可以获得的最大雪球的半径。

示例解释 2

例如，第四个雪球的初始半径为 $10$。在此情况下，无论如何操作，也无法造出比这个更大的雪球。温馨提示，可以接受 $10^{-4}$ 的误差，因此输出 9.9992 或 10.000869120 也算正确。

示例解释 3

即便半径和位置的约束为 $10^9$ 以下，答案可能会超过 $10^9$。

本翻译由 AI 自动生成