# Balloons (Special Judge)

## Problem

Source: 洛谷 P4697, CEOI 2011

### Description

The organizers of CEOI 2011 are planning to hold a party with lots of balloons. There will be $n$ balloons, all sphere-shaped and lying in a line on the ﬂoor.

The balloons are yet to be inﬂated, and each of them initially has zero radius. Additionally, the $i$-th balloon is permanently attached to the ﬂoor at coordinate $x_i$. They are going to be inﬂated sequentially, from left to right. When a balloon is inﬂated, its radius is increased continuously until it reaches the upper bound for the balloon, $r_i$, or the balloon touches one of the previously inﬂated balloons.

The organizers would like to estimate how much air will be needed to inﬂate all the balloons. You are to ﬁnd the ﬁnal radius for each balloon.

### Input

The ﬁrst line of the standard input contains one integer $n (1 \leq n \leq 200 000)$ — the number of balloons.

The next n lines describe the balloons. The $i$-th of these lines contains two integers $x_i$ and $r_i$ $(0 \leq x_i \leq 10^9,1 \leq r_i \leq 10^9)$. You may assume that the balloons are given in a strictly increasing order of the $x$ coordinate.

In test data worth 40 points an additional inequality $n \leq 2000$ holds.

### Output

Your program should output exactly $n$ lines, with the $i$-th line containing exactly one number — the radius of the $i$-th balloon after inﬂating. Your answer will be accepted if it diﬀers from the correct one by no more than 0.001 for each number in the output.

### Sample Input

3
0 9
8 1
13 7


### Sample Output

9.000
1.000
4.694


## Solution

$\text{dist}(i,j) = \sqrt{(x(i) – x(j))^2 + (r(i) – r(j))^2} = r(i) + r(j)$ $\Rightarrow r(i) = \frac{(x(i)–x(j))^2}{4 \times r(j)}$

## Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <cmath>
using namespace std;

const int M = 200005;
int n, top;
double x[M], r[M], q[M];

double Cal(int i, int j) {
return (x[i] - x[j]) * (x[i] - x[j]) / (4 * r[j]);
}

int main() {
cin >> n;
for(int i = 1; i <= n; i++) cin >> x[i] >> r[i];

for(int i = 1; i <= n; i++) {
while(top) {
int j = q[top];
r[i] = min(r[i], Cal(i,j));
if(r[i] >= r[j]) top--;
else break;
}
q[++top] = i;
}
for(int i = 1; i <= n; i++) cout << fixed << setprecision(5) << r[i] << endl;
return 0;
}