← 返回题目列表

AtCoder · s8pc_6_d

D. 雪球

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

最高分数:600 点

问题陈述

有一条很长的直路,从西到东。道路可以用数轴表示,以西为负方向,以东为正方向。

有 N 路上有雪球。 i第一个雪球位于坐标处 X_i 半径为 R_i。我们可以假设所有雪球的形状都是球体。

E869120 试图通过组合其中一些雪球来制造尽可能大的雪球。

当他移动雪球一段距离时 d,它的半径将减少 d。当半径变为零时,雪球就会消失。
此外,他可以在同一坐标处组合两个雪球。当他组合半径的雪球时 r_1 和 r_2,组合雪球的半径将为 \left(r_1^3 + r_2^3\right)^{1/3}.

请计算E869120可以达到的最大可能半径!

约束

  • 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分):没有额外的限制。

输入

输入将从标准输入给出,格式如下。

N
X_1 R_1
X_2 R_2
 :  :
X_N R_N

输出

打印 E869120 可以形成的最大可能半径。
由于它将是一个实数,因此如果绝对或相对误差不超过,您的解决方案将是正确的 10^{-4}.


样本输入 1

2
4 5
7 9

示例输出 1

9.03280211228081065

如果E869120进行以下操作,他可以获得一个半径为1的雪球 737^{1/3} = 9.03280....

  • 移动 1-st 雪球向东按距离 3。那么半径将减少 3 并成为 2.
  • 结合 1-st 和 2-nd 雪球。合并后的半径为 \left(9^3 + 2^3\right)^{1/3} = 9.03280....

这是他能制造的最大的雪球。


示例输入 2

5
3 4
1 4
1 2
9 10
5 3

示例输出 2

9.99999999999999645

4第一个雪球的半径为 10 最初,但在这种情况下他无法获得比这更大的雪球。
另外,本题承认错误小于 10^{-4} (有关详细信息,请参阅“输出”部分),因此打印如下 9.9992 或 `10.000869120' 也是正确的。


示例输入 3

9
815886884 307027576
432574413 156832535
869389414 537542354
8271358 844638329
34762585 93905560
445922147 508315922
476305579 724641385
15004200 341668840
277786703 825590503

示例输出 3

1000677079.68994784

虽然半径和坐标是 10^9 或更少,答案可能超过 10^9.