Rectangles
You will be given n rectangles in the Cartesian plane with sides parallel to the axes. Each rectangle is given by coordinate of lower-left and coordinate of upper-right corner. You should find area of their intersection.
InputThe first line of the standard input contains integer n (2 <= n <= 200 000). Then, in the next n lines there are four numbers x1i, y1i, x2i (x1i < x2i) and y2i (y1i < y2i), 1 <= i <= n. Each coordinate is an integer value from interval [0, 100 000].
For 20% test cases it will be n = 2.
For 40% test cases it will be 2 < n <= 1 000.
For 20% test cases it will be n = 2.
For 40% test cases it will be 2 < n <= 1 000.
OutputThe first line of the standard output should contain one integer that represents the area of intersection of the given rectangles.
Input:
Output:
4
2 2 11 6
5 3 9 8
5 3 10 6
5 1 7 7Output:
6Image: examplerec
Explanation:
Rectangle with lower-left corner (5, 3) and upper-right corner (7, 6) is intersection of the given rectangles.
Input:
Output:
2
0 0 20 20
50 50 100 100Output:
0Explanation:
The rectangles do not have intersection, so, resulting area would be 0.
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.