Overplanting
InterviewTime limit1sMemory limit128 MB
Given up to 10 axis-aligned rectangles, find the total area of their union.
- Level
Medium4 of 10
- Topics
- Geometry, Implementation, Brute force
- Solved
- No attempts yet
Problem
Farmer John has bought a new machine that can plant grass in any axis-aligned rectangular region of his farm (a rectangle whose sides are vertical and horizontal). One day the machine malfunctions and plants grass in not one but () rectangular regions, some of which may overlap.
Given the rectangular regions that were planted with grass, help Farmer John compute the total area of his farm that is now covered with grass.
Input
- Line 1: the integer .
- Lines 2 to : each line contains four space-separated integers describing a rectangular region with upper-left corner and lower-right corner . All coordinates satisfy .
Output
- Line 1: the total area covered by grass.