Hide

Problem E
Sunlight

A core right in Roman tenancy law was the availability of sunlight to everybody, regardless of status. Good sun exposure has a number of health benefits, many of which were known even in those ancient times.

The first act of a Roman city plan reviewer, then, is to survey the proposed structures to measure how well they distribute this precious resource. Given any one avenue of buildings arranged West-to-East, the number of hours for which each building is exposed to sunlight needs to be determined.

For the purpose of simplicity, the number of hours a building is in sunlight is proportional to the fraction of the $180$ degrees of sky visible from its top. Thanks in no small part to the marvels of ancient engineering (and also to the strict nutritional regimes of old) you may assume each building is infinitesimally thin.

Input

  • One line containing one integer $N$ ($1 \leq N \leq 2 \cdot 10^5$): the number of buildings.

  • $N$ further lines each containing two space-separated integers $X_ i$ and $H_ i$ ($1 \leq X, H \leq 10^9$), the location and height respectively, in metres, of the $i^{th}$-most building from the west.

Output

On each of the $N$ lines of output, write one real number to at least 4 decimal places of accuracy: the number of hours for which the peak of the $i$-th building is bathed in sunlight.

Sample Input 1 Sample Output 1
4
1 1
2 2
3 2
4 1
9.0000
12
12.00000
9.0
Sample Input 2 Sample Output 2
5
100 50
125 75
150 100
175 125
200 25
9.0
9.0
9.0
12.0
6.9357496

Please log in to submit a solution to this problem

Log in