最高分数: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
子任务/评分
这个问题被分成几个子任务,如果你的程序打印出准备好的子任务的所有测试用例的正确答案,你将获得子任务的分数。
程序的分数是正确答案的子任务分数的总和。
- (70分):N = 2
- (140分):N \leq 15
- (250分):N \leq 1 \ 000
- (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.