Hide

Problem E
Skyline

/problems/skyline/file/statement/en/img-0001.png
Last time I visited Shanghai I admired its beautiful skyline. It also got me thinking, "Hmm, how much of the buildings do I actually see?" since the buildings wholly or partially cover each other when viewed from a distance.

In this problem, we assume that all buildings have a trapezoid shape when viewed from a distance. That is, vertical walls but a roof that may slope. Given the coordinates of the buildings, calculate how large part of each building that is visible to you (i.e. not covered by other buildings).

Input

The first line contains an integer, $N$ ($2 \le N \le 100$), the number of buildings in the city. Then follow $N$ lines each describing a building. Each such line contains $4$ integers, $x_1$, $y_1$, $x_2$, and $y_2$ ($0 \le x_1 < x_2 \le 10 000, 0 \le y_1, y_2 \le 10 000$). The buildings are given in distance order, the first building being the one closest to you, and so on.

Output

For each building, output a line containing a floating point number between $0$ and $1$, the relative visible part of the building. The absolute error for each building must be within $10^{-6}$.

\includegraphics[width=\linewidth ,height=150pt,keepaspectratio=true]{skyline1}
Figure 1: Figure of the first sample case
Sample Input 1 Sample Output 1
4
2 3 7 5
4 6 9 2
11 4 15 4
13 2 20 2
1.00000000
0.38083333
1.00000000
0.71428571
Sample Input 2 Sample Output 2
5
200 1200 400 700
1200 1400 1700 900
5000 300 7000 900
8200 400 8900 1300
0 1000 10000 800
1.00000000
1.00000000
1.00000000
1.00000000
0.73667852

Please log in to submit a solution to this problem

Log in