Merging Rectangles
Problem
There are N rectangles on the plane with vertices at points with integer coordinates and sides parallel to the coordinate axes. It is necessary to find the area of their union.
Input
The first line of the input file contains the number N (0≤N≤1500). The next N lines contain 4 integers x1, y1, x2, y2 — first the coordinates of the lower left corner of the rectangle, then the upper right (0≤x1≤x2≤109, 0≤y1≤y2≤109). Note that rectangles can degenerate into lines and even into points.
Output
Output a single number — answer to the problem.
| Input |
Output |
|
3
1 1 3 5
5 2 7 4
2 4 6 7
|
23 |
|
2
0 0 2 2
1 3 2 4
|
5 |