4494: 「CEOI2011」Balloons
内存限制：64 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
有 $n$ 个气球，他们一开始都是空的。
接下来，它们会按照从 $1$ 到 $n$ 的顺序依次充气，其中第 $i$ 个气球与地面在 $x_i$ 位置接触。
当气球碰到碰到前面的某个气球，或者达到半径最大限制时，就会停止充气。其中第 $i$ 个气球的半径最大限制为 $r_i$。
现在请你求出，每个气球最终半径是多少。
输入
第一行一个正整数 $n$，表示气球个数。
接下来 $n$ 行，每行两个空格隔开的整数 $x_i,r_i$。
输出
输出 $n$ 行，每行一个浮点数，第 $i$ 行的浮点数表示最终第 $i$ 个气球的半径。
你的答案会被判为正确，当且仅当与答案的绝对误差不超过 $10^{-3}$。
样例输入 复制
3
0 9
8 1
13 7样例输出 复制
9.000
1.000
4.694提示
数据范围：对于 $40\%$ 的数据，保证 $n\le 2\ 000$； 对于 $100\%$ 的数据，保证 $1\le n\le 200\ 000;0\le x_i\le 10^9;1\le r_i\le 10^9;x_1< x_2< \cdots < x_n$。