A zoning map has n axis-aligned rectangles on an integer grid. Each rectangle is given by its lower-left corner (x1, y1) and upper-right corner (x2, y2) with x1 < x2 and y1 < y2. Two rectangles conflict when the region they share has strictly positive area (merely touching along an edge or corner is not a conflict). Count the number of unordered pairs of rectangles that conflict.
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 number of conflicting pairs.
Example 1
Input
3 0 0 3 3 2 2 5 5 10 10 12 12
Expected
1
Explanation
Rectangles 1 and 2 overlap in a 1 by 1 area; rectangle 3 is far away. One conflicting pair.
Example 2
Input
2 0 0 2 2 2 0 4 2
Expected
0
Explanation
The two rectangles meet only along the line x = 2, which has zero area, so there are no conflicts.
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 →