P4697 [CEOI 2011] Balloons

There are $n$ balloons, and they are all empty at the beginning. Next, they will be inflated one by one in order from $1$ to $n$. The $i$-th balloon touches the ground at position $x_i$. A balloon stops inflating when it touches some previous balloon, or when it reaches its maximum radius limit. The maximum radius limit of the $i$-th balloon is $r_i$. Now, please find the final radius of each balloon.

The first line contains a positive integer $n$, which represents the number of balloons. The next $n$ lines each contain two integers $x_i, r_i$ separated by a space.

Output $n$ lines. Each line contains a floating-point number. The floating-point number on the $i$-th line represents the final radius of the $i$-th balloon. Your answer will be judged correct if and only if the absolute error from the correct answer does not exceed $10^{-3}$.

For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 200\,000$, $0 \le x_i \le 10^9$, $1 \le r_i \le 10^9$, and $x_1 < x_2 < \cdots < x_n$. Translated by ChatGPT 5