CF 102697051 - The Convergence of Two Tetra-sided Polygons, Known as Rectangles

CF 102697051 - The Convergence of Two Tetra-sided Polygons, Known as Rectangles

Rating: -
Tags: -
Solve time: 1m
Verified: yes

Solution

Problem Understanding

We are given two axis-aligned rectangles. Each rectangle is described by two opposite corners, so one line contains four integers x1 y1 x2 y2 for the first rectangle, and the next line contains the same information for the second rectangle. The coordinates may be given in either order, so the first thing a solution should do is convert every rectangle into its left, right, bottom, and top boundaries.

The required answer is YES when the two rectangle perimeters have at least one point in common, and NO otherwise. This interpretation follows the problem's special condition that two identical rectangles intersect, while a rectangle strictly inside another rectangle does not intersect it when their perimeters are disjoint.

The official statement gives a one-second time limit and 256 MB of memory. It does not publish explicit coordinate bounds, so there is no useful large n to optimize over. The input itself always contains only two rectangles, which means the intended solution should be constant time and should depend only on the eight coordinates.

The main edge case is strict containment. Consider

0 0 10 10
2 2 8 8

The correct output is

NO

The second rectangle is completely inside the first one, and their perimeters never touch. A careless solution that only checks whether the two rectangles' x and y intervals overlap would print YES, because both projections overlap completely.

The opposite situation is containment with a touching boundary:

0 0 10 10
0 2 8 8

The correct output is

YES

The second rectangle touches the first one along the left side. The containment is not strict because the two rectangles share boundary points. Using strict inequalities when detecting containment handles this case correctly.

Another important case is two identical rectangles:

0 0 5 5
0 0 5 5

The correct output is

YES

A strict-containment test must not classify identical rectangles as containment, because every corresponding boundary point belongs to both rectangles. The statement explicitly says overlapping identical rectangles count as intersecting.

Finally, rectangles can intersect at exactly one corner:

0 0 2 2
2 2 5 5

The correct output is

YES

The interval comparisons must be inclusive. Replacing <= by < would incorrectly reject this case.

Approaches

A direct brute-force idea is to inspect every integer point in the combined bounding box of the two rectangles and check whether that point lies on both perimeters. Because all input coordinates are integers and the rectangles are axis-aligned, any intersection between their boundaries has integer coordinates. For a bounding box containing W + 1 possible integer x-coordinates and H + 1 possible integer y-coordinates, the worst case examines exactly (W + 1)(H + 1) points. With large coordinate ranges this can become arbitrarily expensive, and the problem does not give a coordinate bound that would make such enumeration reasonable.

A more geometric brute-force method could check all pairs of boundary segments. There are four sides per rectangle, giving exactly 16 segment pairs. That method is already constant time and would be accepted, but it requires more geometry code than necessary.

The key observation is that an axis-aligned rectangle is completely described by two one-dimensional intervals. The rectangles can only have intersecting perimeters if their x-ranges overlap and their y-ranges overlap. However, interval overlap alone is not sufficient because strict containment also gives overlapping projections while the perimeters remain separate.

The useful reduction is to perform two tests. First, check that the rectangles have overlapping x and y intervals, including touching endpoints. Second, check that neither rectangle is strictly inside the other. If both conditions hold, the perimeters must meet somewhere. If either interval is disjoint, the rectangles are separated. If one rectangle is strictly inside the other, the two perimeters are disjoint.

Approach	Time Complexity	Space Complexity	Verdict
Integer-point enumeration	O(W · H)	O(1)	Too slow for large coordinates
Pairwise edge intersection	O(1)	O(1)	Accepted
Interval overlap + containment	O(1)	O(1)	Accepted

Algorithm Walkthrough

1. Read the two opposite corners of each rectangle and normalize them. For a rectangle with corners (x1, y1) and (x2, y2), define left = min(x1, x2), right = max(x1, x2), bottom = min(y1, y2), and top = max(y1, y2). This removes any dependence on which opposite corner was listed first.
2. Check whether the x-projections overlap using max(left1, left2) <= min(right1, right2). The inequality is inclusive because sharing a vertical boundary or a single x-coordinate is still compatible with an intersection.
3. Check whether the y-projections overlap in the same way, using max(bottom1, bottom2) <= min(top1, top2). If either projection is disjoint, the rectangles cannot have a common boundary point.
4. Check whether the first rectangle is strictly inside the second one. This happens exactly when left2 < left1, right1 < right2, bottom2 < bottom1, and top1 < top2.
5. Check the symmetric condition for the second rectangle being strictly inside the first one.
6. Print YES exactly when the projections overlap and neither strict-containment condition is true. The strict inequalities are what distinguish true containment from rectangles that merely touch along an edge or corner.

Why it works. Suppose the algorithm prints YES. The x and y projections overlap, so the two rectangles occupy a common region of the plane or touch at its boundary. Since neither rectangle is strictly contained inside the other, their boundaries cannot be completely separated. Their perimeters must consequently share at least one point.

Conversely, suppose the rectangles' perimeters intersect. Their x and y projections necessarily overlap, because a common boundary point has the same x-coordinate and y-coordinate in both rectangles. Also, neither rectangle can be strictly inside the other, because strict containment would place the inner perimeter entirely away from the outer perimeter. Thus every genuine intersection passes both tests, and the algorithm prints YES.

Python Solution

import sys
input = sys.stdin.readline

def normalize(rect):
    x1, y1, x2, y2 = rect
    left = min(x1, x2)
    right = max(x1, x2)
    bottom = min(y1, y2)
    top = max(y1, y2)
    return left, right, bottom, top

def solve():
    r1 = normalize(list(map(int, input().split())))
    r2 = normalize(list(map(int, input().split())))

    left1, right1, bottom1, top1 = r1
    left2, right2, bottom2, top2 = r2

    x_overlap = max(left1, left2) <= min(right1, right2)
    y_overlap = max(bottom1, bottom2) <= min(top1, top2)

    first_inside = (
        left2 < left1 and
        right1 < right2 and
        bottom2 < bottom1 and
        top1 < top2
    )

    second_inside = (
        left1 < left2 and
        right2 < right1 and
        bottom1 < bottom2 and
        top2 < top1
    )

    if x_overlap and y_overlap and not first_inside and not second_inside:
        print("YES")
    else:
        print("NO")

if __name__ == "__main__":
    solve()

The normalize function converts each pair of opposite corners into the canonical representation (left, right, bottom, top). Without this step, comparisons would have to handle four possible orientations of each input rectangle.

The x_overlap and y_overlap expressions use inclusive comparisons. This is necessary because touching at an edge or corner counts as an intersection. For example, [0, 2] and [2, 5] overlap at the endpoint 2.

The containment checks use strict inequalities. If a boundary coordinate is equal, the rectangles touch and containment is not strict. This is exactly what we need for cases such as one rectangle sharing the outer rectangle's left edge.

Python integers do not overflow, so the solution remains safe even for coordinates much larger than the range of a 32-bit integer. No loops or auxiliary data structures are needed.

Worked Examples

For the provided sample, the input is

-5 -5 5 5
4 4 8 8

After normalization, the first rectangle is [-5, 5] × [-5, 5], while the second is [4, 8] × [4, 8].

Step	Rectangle 1	Rectangle 2	x overlap	y overlap	Strict containment	Result
Normalize	[-5,5] × [-5,5]	[4,8] × [4,8]
Check projections	[-5,5]	[4,8]	Yes	Yes	No	YES

The x-ranges overlap from 4 to 5, and the y-ranges overlap from 4 to 5. Neither rectangle contains the other, so the two perimeters cross around the overlapping corner region. The correct output is YES, matching the official sample.

For a strict-containment example,

0 0 10 10
2 2 8 8

the normalized rectangles are already in the required order.

Step	Rectangle 1	Rectangle 2	x overlap	y overlap	Strict containment	Result
Normalize	[0,10] × [0,10]	[2,8] × [2,8]
Check projections	[0,10]	[2,8]	Yes	Yes	Rectangle 2 inside Rectangle 1	NO

Both projections overlap, but every side of the second rectangle lies strictly inside the first rectangle. The perimeters have no common point, so the answer is NO.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	Only a fixed number of coordinate comparisons are performed
Space	O(1)	Only the coordinates and a few Boolean values are stored

The problem has only two rectangles, so there is no input-size-dependent loop. The official time limit is one second and the memory limit is 256 MB, while the published statement gives no large coordinate-array structure to process. A constant-time solution is comfortably within both limits.

Test Cases

# helper: run solution on input string, return output string
import sys
import io

def solve():
    def normalize(rect):
        x1, y1, x2, y2 = rect
        return min(x1, x2), max(x1, x2), min(y1, y2), max(y1, y2)

    r1 = normalize(list(map(int, input().split())))
    r2 = normalize(list(map(int, input().split())))

    left1, right1, bottom1, top1 = r1
    left2, right2, bottom2, top2 = r2

    x_overlap = max(left1, left2) <= min(right1, right2)
    y_overlap = max(bottom1, bottom2) <= min(top1, top2)

    first_inside = (
        left2 < left1 and right1 < right2 and
        bottom2 < bottom1 and top1 < top2
    )

    second_inside = (
        left1 < left2 and right2 < right1 and
        bottom1 < bottom2 and top2 < top1
    )

    print("YES" if x_overlap and y_overlap
          and not first_inside and not second_inside else "NO")

def run(inp: str) -> str:
    global input

    old_stdin = sys.stdin
    old_input = input

    try:
        sys.stdin = io.StringIO(inp)
        input = sys.stdin.readline

        old_stdout = sys.stdout
        sys.stdout = io.StringIO()
        try:
            solve()
            return sys.stdout.getvalue()
        finally:
            sys.stdout = old_stdout
    finally:
        sys.stdin = old_stdin
        input = old_input

# Provided sample
assert run("-5 -5 5 5\n4 4 8 8\n") == "YES\n", "sample 1"

# Custom case 1: minimum-size non-degenerate rectangles
assert run("0 0 1 1\n3 3 4 4\n") == "NO\n", "minimum-size disjoint rectangles"

# Custom case 2: identical rectangles
assert run("0 0 5 5\n0 0 5 5\n") == "YES\n", "identical rectangles"

# Custom case 3: strict containment
assert run("0 0 10 10\n2 2 8 8\n") == "NO\n", "strict containment"

# Custom case 4: boundary touch with very large coordinates
assert run("-1000000000000 -1000000000000 0 0\n0 0 1000000000000 1000000000000\n") == "YES\n", "corner touch"

Test input	Expected output	What it validates
0 0 1 1 and 3 3 4 4	NO	Smallest ordinary non-degenerate rectangles and disjoint projections
0 0 5 5 and 0 0 5 5	YES	Identical rectangles must count as intersecting
0 0 10 10 and 2 2 8 8	NO	Strict containment must not be mistaken for intersection
-10^12 -10^12 0 0 and 0 0 10^12 10^12	YES	Boundary equality, corner touching, and large coordinates

Edge Cases

For strict containment,

0 0 10 10
2 2 8 8

normalization leaves both rectangles unchanged. The x-ranges [0,10] and [2,8] overlap, as do the y-ranges. The second rectangle satisfies 0 < 2, 8 < 10, 0 < 2, and 8 < 10, so it is strictly inside the first. The algorithm rejects the pair and prints NO.

For boundary contact,

0 0 10 10
0 2 8 8

the x-ranges overlap at more than one point and the y-ranges overlap. The second rectangle is not strictly inside the first because its left boundary equals the first rectangle's left boundary. The algorithm therefore prints YES, correctly treating the shared vertical edge as an intersection.

For identical rectangles,

0 0 5 5
0 0 5 5

both containment tests are false because all corresponding boundaries are equal rather than strictly nested. The projections overlap, so the algorithm prints YES.

For a single-corner intersection,

0 0 2 2
2 2 5 5

the x-ranges intersect at x = 2, and the y-ranges intersect at y = 2. Both comparisons use <=, so the shared point (2, 2) is accepted. Neither rectangle is strictly contained in the other, giving the correct output YES.

For reversed corner order,

5 5 0 0
8 8 4 4

normalization converts the rectangles to [0,5] × [0,5] and [4,8] × [4,8]. The rest of the algorithm is identical to the ordinary orientation and produces YES. This is why normalizing the coordinates at the beginning is preferable to trying to handle every possible input orientation separately.