Skyline

Interview

Time limit1sMemory limit128 MB

Summary

We have N trapezoidal buildings listed from nearest to farthest. For each building, we must compute the fraction of its area that remains visible, i.e., the part of the trapezoid not hidden by any closer building. The presence of overlapping sloped roofs makes the computation nontrivial: for a given building we need to determine, for each horizontal coordinate, the maximum roof height among all closer buildings. Then the visible area is the integral, over the building’s own range [x1, x2], of the positive part of the difference between the building's top edge (roof) and that maximum height.For

Level: Easy3 of 10
Topics: Geometry, Intervals, Divide and conquer, Dynamic programming
Solved: No attempts yet

Problem

When you look at a city skyline from a distance, the buildings partly or wholly cover one another, which makes you wonder how much of each building you actually see.

In this problem we assume that, seen from a distance, every building has the shape of a trapezoid: the side walls are vertical, but the roof may slope.

Each building is a trapezoid standing on the ground:

Left wall: the vertical segment from $(x_1, 0)$ to $(x_1, y_1)$
Right wall: the vertical segment from $(x_2, 0)$ to $(x_2, y_2)$
Roof: the segment from $(x_1, y_1)$ to $(x_2, y_2)$
Base: the segment along the ground from $(x_1, 0)$ to $(x_2, 0)$

The buildings are given in order of distance, nearest first. Seen from the front, a nearer building hides everything behind it up to its own outline. For each building, compute the fraction of its area that stays visible (that is, not covered by any nearer building).

Input

The first line contains the number of buildings $N$ ( $2 \le N \le 100$ ).

Each of the next $N$ lines contains four integers $x_1$ , $y_1$ , $x_2$ , $y_2$ describing one building ( $0 \le x_1 < x_2 \le 10000$ , $0 < y_1, y_2 \le 10000$ ).

The buildings are listed in order of distance: the first is the one closest to you, and so on.

Output

For each building, print on its own line the visible fraction of that building (a value between 0 and 1), rounded to exactly 8 digits after the decimal point.

The test data guarantees that the exact value never lies on a rounding boundary, so any correct computation produces the same 8-digit result.

Hint

Figure 1: The layout of the first test case.

Examples2

Example 1

Input

Expected output

Example 2

Input

5
200 1200 400 700
1200 1400 1700 900
5000 300 7000 900
8200 400 8900 1300
0 1000 10000 800

Expected output