#C5911. Geographical Zones
Geographical Zones
Geographical Zones
This problem involves managing geographical zones represented by rectangular areas. You need to implement a system that supports three main operations:
add x1 y1 x2 y2
: Add a new rectangular zone defined by its bottom-left point \( (x_1, y_1) \) and its top-right point \( (x_2, y_2) \).contains x y
: Check if the point \( (x, y) \) is contained in any of the existing zones. If so, output "YES"; otherwise, output "NO".minimal
: Determine the minimal rectangle that contains all added zones and output its bottom-left and top-right points asx1 y1 x2 y2
. If no rectangle exists, this operation produces no output.
All input is provided via standard input and all output must be sent to standard output. Make sure your solution processes each operation in the order given.
inputFormat
The first line contains a single integer \( m \) representing the number of operations.
The following \( m \) lines each contain an operation in one of the following formats:
- add x1 y1 x2 y2: Add a rectangle zone with bottom-left coordinates \( (x_1, y_1) \) and top-right coordinates \( (x_2, y_2) \).
- contains x y: Check if the point \( (x, y) \) is inside any existing rectangle.
- minimal: Output the minimal rectangle that encloses all rectangles in the form
x1 y1 x2 y2
.
outputFormat
For each contains
operation output "YES" or "NO" on a separate line. For each minimal
operation that finds at least one rectangle, output a single line with the coordinates x1 y1 x2 y2
of the minimal enclosing rectangle. Operations that do not generate output should simply be ignored.
6
add 1 1 4 4
add 2 2 6 5
contains 3 3
contains 6 6
minimal
add 7 3 8 4
YES
NO
1 1 6 5
</p>