#P4697. [CEOI2011] Balloons

[CEOI2011] Balloons

题目描述

nn 个气球,他们一开始都是空的。

接下来,它们会按照从 11nn 的顺序依次充气,其中第 ii 个气球与地面在 xix_i 位置接触。

当气球碰到碰到前面的某个气球,或者达到半径最大限制时,就会停止充气。其中第 ii 个气球的半径最大限制为 rir_i

现在请你求出,每个气球最终半径是多少。

输入格式

第一行一个正整数 nn,表示气球个数。

接下来 nn 行,每行两个空格隔开的整数 xi,rix_i,r_i

输出格式

输出 nn 行,每行一个浮点数,第 ii 行的浮点数表示最终第 ii 个气球的半径。

你的答案会被判为正确,当且仅当与答案的绝对误差不超过 10310^{-3}​​。

3
0 9
8 1
13 7
9.000
1.000
4.694

提示

对于 100%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$。