问题陈述
圆圈岛以其神秘的形状而闻名: 它是一个完全平坦的岛屿,其形状是圆的并集,其中心位于 $x$ 轴及其内部区域。
圆岛之王计划在圆岛上建造一个大型广场,以庆祝他登基五十周年。 国王想让广场尽可能大。 广场的整个区域必须位于圆岛的表面上,但圆岛的任何区域都可以用作广场。 他还要求正方形的形状是正方形(当然!)并且正方形的至少一侧平行于$x$轴。
你,圆圈岛的部长,现在被命令建造广场。 首先,国王想知道正方形有多大。 您将获得构成圆岛的圆圈的位置和半径。 回答最大可能的正方形的边长。
$N$ 个圆按其中心 $x$ 坐标的升序给出。 您可以假设对于所有 $i$ ($1 \le i \le N-1$),第 $i$-th 和 $(i+1)$-st 圆彼此重叠。 您还可以假设没有任何圆与其他圆完全重叠。
[原图]
图 1:圆岛的形状和样本输入的测试用例 #1 的最大可能正方形之一
输入
输入由多个数据集组成。数据集数量不超过 30 美元。 每个数据集的格式如下。
$N$
$X_1$ $R_1$
:
:
$X_N$ $R_N$
数据集的第一行包含一个整数 $N$ ($1 \le N \le 50{,}000$),即构成 Circles Island 的圆圈数。 下面的每行 $N$ 描述一个圆。 $(i+1)$-st 行包含两个整数 $X_i$ ($-100{,}000 \le X_i \le 100{,}000$) 和 $R_i$ ($1 \le R_i \le 100{,}000$)。 $X_i$ 表示第 $i$ 个圆的中心的 $x$ 坐标,$R_i$ 表示第 $i$ 个圆的半径。 每个圆的$y$坐标为$0$,即第$i$个圆的圆心位于($X_i$,$0$)处。
您可以做出以下假设。
- 对于所有 $i$ ($1 \le i \le N-1$),$X_i$ 严格小于 $X_{i+1}$。
- 对于所有$i$ ($1 \le i \le N-1$),第$i$个圆和第$(i+1)$个圆至少有一个公共点($X_{i+1} - X_i \le R_i + R_{i+1}$)。
- 每个圆至少有一个点不在任何其他圆的内部或边界上。
输入的结尾由包含零的行指示。
输出
对于每个数据集,输出一行,其中包含面积最大的正方形的边长。 输出的绝对或相对误差不得超过 $10^{-4}$。
示例输入
2 0 8 10 8 2 0 7 10 7 0
样本输入的输出
12.489995996796796 9.899494936611665