← 返回题目列表

AtCoder · icpc2014autumn_e

E. 方中有圆

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

问题陈述

圆圈岛以其神秘的形状而闻名: 它是一个完全平坦的岛屿,其形状是圆的并集,其中心位于 $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