Workers spread n rectangular tarps over a flat field. Tarp i is an axis-aligned rectangle covering all points with x1 <= x <= x2 and y1 <= y <= y2 (with x1 < x2 and y1 < y2). Tarps may overlap. Compute the total area of the field covered by at least one tarp (the area of the union). Overlapping area is counted once.
Line 1: an integer n.
Next n lines: four integers x1 y1 x2 y2 describing one rectangle.
A single integer: the area of the union of all rectangles.
Example 1
Input
2 0 0 2 2 1 1 3 3
Expected
7
Explanation
Each rectangle has area 4; they overlap in the 1x1 square [1,2]x[1,2], so the union is 4 + 4 - 1 = 7.
Example 2
Input
2 0 0 2 2 5 5 7 7
Expected
8
Explanation
The rectangles are disjoint, so the union area is 4 + 4 = 8.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →