409029: GYM103416 I Restricted Track

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

I. Restricted Tracktime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

We have a track that is infinite in one direction.

At the begging of the track, we have a car with an initial speed of $$$v=0$$$ m/s. Also, the car has an acceleration of $$$a$$$ m$$$/s^2$$$, which we can change at any moment of time to a value in the range [1, -1] m$$$/s^2$$$. The speed of the car can reach any value in the range (-$$$\infty$$$, $$$\infty$$$) m/s

We are given $$$n$$$ requests. In each request, a new restriction $$$(t, r)$$$ is added: At the moment when $$$t$$$ seconds have passed from the start of the race, the speed of the car should satisfy $$$v \leq r$$$ (at that exact moment).

After each request, you need to print the maximum distance that the car can reach at the moment when all restrictions are passed.

Input

The first line of the input contains a single integer $$$ n $$$ ($$$ 1 \leq n \leq 2 00 000 $$$) — the number of requests.

Each of the next n lines contains two integers $$$ t_i $$$, $$$ r_i $$$ ($$$ 1 \leq t_i \leq 10 ^ 9 $$$), ($$$ 0 \leq r_i \leq 10 ^ 9 $$$) - a moment in time, and a speed limit.

Output

For each request, print the answer to how far the car can go at the moment when it passes all the restrictions. The absolute error of your answer must not exceed ($$$10^{-6}$$$).

ExampleInput
3
1 3
3 3
1 0
Output
0.500000000
4.500000000
2.250000000

加入题单

上一题 下一题 算法标签: