Problem B. 2. Counting rectangles
Input file name: standard input
Output file name: standard output
Time limit: 1 s
Memory limit: 1024 MB
Output file name: standard output
Time limit: 1 s
Memory limit: 1024 MB
An architect is drafting a blueprint on an infinite 2D plane. They draw the exact outlines of N rectangles with sides parallel to the X and Y axes and integer corner coordinates.
Important: The architect only draws the borders (wireframes) of these rectangles; the internal areas are not filled. When line segments overlap, they merge into a single line segment.
Your task is to calculate the total number of distinctly visible rectangles in the final drawing. A valid rectangle is defined by any four corner points connected by continuous, unbroken horizontal and vertical line segments.
Important: The architect only draws the borders (wireframes) of these rectangles; the internal areas are not filled. When line segments overlap, they merge into a single line segment.
Your task is to calculate the total number of distinctly visible rectangles in the final drawing. A valid rectangle is defined by any four corner points connected by continuous, unbroken horizontal and vertical line segments.
Input
The first line contains a single integer N (1 \le N \le 100).
The following N lines each contain four space-separated integers x_1, y_1, x_2, and y_2 (-100 \le x_1, y_1, x_2, y_2 \le 100; x_1 < x_2 and y_1 > y_2), representing the top-left and bottom-right corners respectively.
The following N lines each contain four space-separated integers x_1, y_1, x_2, and y_2 (-100 \le x_1, y_1, x_2, y_2 \le 100; x_1 < x_2 and y_1 > y_2), representing the top-left and bottom-right corners respectively.
Output
Print a single integer: the total number of distinct rectangles present in the final drawing. It is guaranteed that output will be less than 10^6.
Examples
| standard input | standard output |
|---|---|
| 2 0 2 2 0 1 3 3 1 | 3 |
Note
Explanation for the example case:
Two overlapping rectangles can create additional rectangles where their boundaries intersect. In this case, the two original rectangles plus the new rectangle formed by their intersection results in 3 total rectangles:
Two overlapping rectangles can create additional rectangles where their boundaries intersect. In this case, the two original rectangles plus the new rectangle formed by their intersection results in 3 total rectangles:
