#2487. 「CEOI2011」Balloons

内存限制:64 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: diamond_duke

题目描述

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