#K84812. Overlapping Rectangles
Overlapping Rectangles
Overlapping Rectangles
Given a list of rectangles defined by their top-left and bottom-right coordinates, determine whether any two rectangles overlap.
A rectangle is represented by four integers: x₁, y₁, x₂, and y₂, where (x₁, y₁) is the top-left corner and (x₂, y₂) is the bottom-right corner. Two rectangles overlap if they share any area. The condition for non-overlapping can be written in LaTeX as:
$$x_2 < xx_1 \quad \text{or} \quad xx_2 yy_1 \quad \text{or} \quad yy_2 > y_1$$
If none of these conditions hold, then the rectangles overlap.
For each test case, output "Overlapping" if there is at least one pair of overlapping rectangles; otherwise, output "Not Overlapping".
inputFormat
The input consists of multiple test cases. For each test case:
- The first line contains an integer n representing the number of rectangles.
- The next n lines each contain four integers: x₁ y₁ x₂ y₂, representing a rectangle's coordinates.
A line containing -1
indicates the end of input.
outputFormat
For each test case, output a single line containing either "Overlapping" if any two rectangles overlap, or "Not Overlapping" if none of them overlap.
## sample3
1 4 3 2
2 3 5 1
6 4 8 2
2
0 2 2 0
1 3 3 1
-1
Overlapping
Overlapping
</p>