Unreal Estate

Time limit10sMemory limit128 MB

Summary

Given up to 5000 rectangles with real coordinates, compute the total area their union covers, counting overlaps once, and print it rounded to two decimals.

Level: Medium7 of 10
Topics: Geometry, Sorting, Divide and conquer, Segment tree
Solved: No attempts yet

Problem

A dishonest landowner is selling off plots of land. He sells them as large rectangular plots, but many of the plots overlap, so he is really selling the same land multiple times! It is not real estate, it is unreal estate!

Given a list of the (possibly overlapping) rectangular plots the landowner has sold, determine the total actual area of land they cover. Overlapping regions are counted only once.

Input

The input contains several test cases. Each test case begins with a line containing a single integer $n$ ( $0 < n \le 5000$ ), the number of plots sold. Each of the next $n$ lines describes one rectangular plot as four real numbers:

x1 y1 x2 y2

where $(x_1, y_1)$ is the southwest (bottom-left) corner and $(x_2, y_2)$ is the northeast (top-right) corner, with $-1000 \le x_1 < x_2 \le 1000$ and $-1000 \le y_1 < y_2 \le 1000$ . Every plot has an area of at least $1$ .

The input ends with a line containing a single $0$ .

Output

For each test case, output a single real number: the total actual area covered by all of the rectangular plots. Print this value rounded to exactly two decimal places. Do not print any spaces, and do not print any blank lines between outputs.

Examples8

Example 1

Input

2
0 0 100 100
30 30 60 60
2
0 100 300 200
100 0 200 300
0

Expected output

10000.00
50000.00

Example 2
Input
```
1
-10 -20 -5 -5
0
```
Expected output
```
75.00
```
Example 3
Input
```
2
0 0 10 10
20 20 30 30
0
```
Expected output
```
200.00
```

Example 4

Input

2
-1000 -1000 1000 1000
-500 -500 500 500
0

Expected output

4000000.00

Example 5
Input
```
2
0 0 2.5 2.5
1.5 1.5 4 4
0
```
Expected output
```
11.50
```
Example 6
Input
```
2
0 10 30 20
10 0 20 30
0
```
Expected output
```
500.00
```

Example 7

Input

Expected output

25.00
40.00

Example 8

Input

1
0 0 1 1
1
-1000 -1000 -999 0
0

Expected output

1.00
1000.00