#K84812. Overlapping Rectangles

    ID: 36503 Type: Default 1000ms 256MiB

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.

## sample
3
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>