Area of Overlapping Rectangles

Difficulty: 2300 6000 ms 128 MB

geometry sweep-line

Print the total area covered by the union of N axis-aligned rectangles (overlaps counted once).

Input: the first line has N; each of the next N lines has x1 y1 x2 y2 (lower-left and upper-right corners).

Output: the area of the union.

Constraints:

• 1 ≤ N ≤ 10³
• |coordinates| ≤ 10⁴

Sample Tests

2
0 0 2 2
1 1 3 3

7

1
0 0 5 5

25

Read the Editorial