A floorplan is drawn as n axis-aligned rectangular rooms on an integer grid. Rectangles may overlap. Each rectangle is given by its lower-left corner (x1, y1) and its upper-right corner (x2, y2) with x1 < x2 and y1 < y2. Compute the total area covered by at least one rectangle (regions covered by several rectangles are counted only once).
Line 1: an integer n, the number of rectangles.
Next n lines: four integers x1 y1 x2 y2 describing a rectangle.
A single integer: the area of the union.
Example 1
Input
2 0 0 3 3 2 2 5 5
Expected
17
Explanation
Each rectangle has area 9 and they share a 1 by 1 corner, so the union is 9 + 9 - 1 = 17.
Example 2
Input
1 0 0 4 2
Expected
8
Explanation
A single 4 by 2 rectangle covers 8 units of area.
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 →