Problem G
Unreal Estate
A dishonest landowner is selling off plots of land. He’s selling it in large, rectangular plots, but many of the plots overlap, so he’s actually selling the same land multiple times! It’s not real estate, it’s unreal estate!
Given a description of the possibly overlapping rectangular plots of land that the dishonest landowner has sold, determine the total actual area of land covered by them.
Input
There will be a single test case in the input. Each test case will begin with a line with a single integer $n$ ($0 < n \le 5\, 000$), indicating the number of plots of land sold. The next $n$ lines will each have a description of a rectangular plot of land, consisting of four real numbers with at most two decimals after the decimal point:
x1 y1 x2 y2
where $(x_1,y_1)$ is the southwest corner, and $(x_2,y_2)$ is the northeast corner ($-1\, 000 \le x_1 < x_2 \le 1\, 000$, $-1\, 000 \le y_1 < y_2 \le 1\, 000$).
Output
Output a single real number, which represents the total actual area covered by all of the rectangular plots of land. Output this number with exactly two decimal places, rounded.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 0 0 100 100 30 30 60 60 |
10000.00 |
| Sample Input 2 | Sample Output 2 |
|---|---|
2 0.00 100.00 300.00 200.00 100.00 0.00 200.00 300.00 |
50000.00 |
