CF 135B - Rectangle and Square

Rating: 1600
Tags: brute force, geometry, math
Solve time: 2m 3s
Verified: yes

Solution

Problem Understanding

We are given eight distinct points on the plane. The task is to split them into two disjoint groups of four points each.

One group must form a square. The other group must form a rectangle. A square is also allowed for the rectangle group, so the second shape only needs to satisfy the rectangle conditions.

The points may appear in any order, and the shapes are not necessarily axis-aligned. Rotated squares and rectangles are fully valid.

The output must either report that such a partition exists, together with the indices of the corresponding points, or report that no valid partition exists.

The input size is extremely small. We only have eight points, which means brute force over subsets is completely realistic. There are only

$$\binom{8}{4} = 70$$

ways to choose four points for the square. Once those are fixed, the remaining four automatically belong to the rectangle.

This immediately suggests that the real challenge is geometric validation, not optimization.

The dangerous part of the problem is shape recognition. A careless implementation can easily misclassify invalid configurations as valid ones.

Consider these points:

All pairwise distances are not equal, but if someone only checks for "two distinct distances", this degenerate line could accidentally pass. Both the square and rectangle must have positive area.

Another common mistake is assuming the points arrive in cyclic order. For example:

These are the vertices of a square, but in shuffled order. Any algorithm that directly checks adjacent sides without considering permutations will fail.

Rotated figures also matter. This rectangle is valid:

The sides are not parallel to the axes, so checking only x and y coordinates is incorrect.

The safest approach is to work entirely with distances and vector dot products, because those properties remain valid regardless of rotation or ordering.

Approaches

The brute force idea is straightforward. We try every subset of four points as the square candidate. The remaining four points become the rectangle candidate. Then we independently verify whether the chosen groups really form the required shapes.

Since there are only 70 subsets, even expensive geometric checks are fast enough.

The real question becomes how to verify a square or rectangle robustly.

A naive geometric approach is to sort points angularly around the center and then test side lengths and right angles. That works, but it is unnecessarily fragile. Floating point issues and ordering complications make the implementation harder than needed.

A cleaner observation is that both squares and rectangles have simple diagonal properties.

For a rectangle:

The diagonals have equal length.
The diagonals share the same midpoint.
The area is non-zero.

For a square, we additionally require:

All four sides equal.
Diagonals equal.
Diagonals longer than sides.

Instead of reconstructing polygon orderings, we can directly analyze pairwise distances.

For four points, there are exactly six pairwise squared distances.

A valid square produces:

Four equal smaller distances, the sides.
Two equal larger distances, the diagonals.
The diagonal length equals twice the side length in squared form.

A valid rectangle produces:

Two pairs of equal side lengths.
Two equal diagonals.
Positive area.

An even cleaner rectangle check comes from permutations. Since there are only 24 orderings of four points, we can simply try all possible cyclic orders and test:

$$\overrightarrow{AB} \cdot \overrightarrow{BC} = 0$$

and

$$|AB| > 0,\quad |BC| > 0$$

with opposite sides equal automatically implied.

Because the search space is tiny, the permutation approach is perfectly acceptable and extremely reliable.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force with geometric reconstruction	$O(70 \cdot 24)$	$O(1)$	Accepted
Optimal subset brute force with robust checks	$O(70 \cdot 24)$	$O(1)$	Accepted

Algorithm Walkthrough

Read the eight points and store their coordinates together with their original indices.
Enumerate every subset of four indices as the candidate square.
Construct the complementary subset of four indices for the rectangle candidate.
Check whether the first group forms a square.

We compute all six pairwise squared distances.

A valid square must produce exactly two distinct positive values:

$${s,s,s,s,d,d}$$

where

$$d = 2s$$

The smaller value represents the sides, and the larger value represents the diagonals. 5. Check whether the second group forms a rectangle.

We try all permutations of the four points as possible cyclic orderings.

For an ordering $A,B,C,D$, we verify:

$$\overrightarrow{AB} \cdot \overrightarrow{BC} = 0$$

which guarantees a right angle.

Then we verify:

$$|AB| = |CD|$$

and

$$|BC| = |DA|$$

together with positive side lengths. 6. If both checks succeed, print "YES" and the corresponding point indices. 7. If no partition works after testing all subsets, print "NO".

Why it works

The algorithm exhaustively tries every possible division of the eight points into two groups of four. No valid answer can escape this enumeration.

The square test is correct because any square always has four equal sides and two equal diagonals, and those are the only pairwise distances that appear. Degenerate configurations fail because side lengths must be positive.

The rectangle test is correct because every rectangle has four right angles and opposite sides equal. Trying all permutations guarantees that eventually we encounter the true cyclic order of the rectangle vertices.

Since every candidate partition is checked exactly against the mathematical definitions of the shapes, the algorithm cannot accept an invalid configuration or reject a valid one.

Python Solution

import sys
from itertools import combinations, permutations

input = sys.stdin.readline

def dist2(a, b):
    dx = a[0] - b[0]
    dy = a[1] - b[1]
    return dx * dx + dy * dy

def is_square(points):
    dists = []

    for i in range(4):
        for j in range(i + 1, 4):
            dists.append(dist2(points[i], points[j]))

    dists.sort()

    if dists[0] == 0:
        return False

    return (
        dists[0] == dists[1] == dists[2] == dists[3]
        and dists[4] == dists[5]
        and dists[4] == 2 * dists[0]
    )

def dot(ax, ay, bx, by):
    return ax * bx + ay * by

def is_rectangle(points):
    for p in permutations(points):
        a, b, c, d = p

        abx = b[0] - a[0]
        aby = b[1] - a[1]

        bcx = c[0] - b[0]
        bcy = c[1] - b[1]

        cdx = d[0] - c[0]
        cdy = d[1] - c[1]

        dax = a[0] - d[0]
        day = a[1] - d[1]

        if dot(abx, aby, bcx, bcy) != 0:
            continue

        if dist2(a, b) == 0 or dist2(b, c) == 0:
            continue

        if dist2(a, b) != dist2(c, d):
            continue

        if dist2(b, c) != dist2(d, a):
            continue

        return True

    return False

def solve():
    pts = [tuple(map(int, input().split())) for _ in range(8)]

    indices = list(range(8))

    for square_ids in combinations(indices, 4):
        square_set = set(square_ids)

        rect_ids = [i for i in indices if i not in square_set]

        square_points = [pts[i] for i in square_ids]
        rect_points = [pts[i] for i in rect_ids]

        if is_square(square_points) and is_rectangle(rect_points):
            print("YES")
            print(*[i + 1 for i in square_ids])
            print(*[i + 1 for i in rect_ids])
            return

    print("NO")

solve()

The solution has two independent geometry validators.

The square checker uses the pairwise distance characterization. Since squared distances avoid square roots, all computations stay in integers. This completely removes floating point precision issues.

The rectangle checker uses permutations because the input order is arbitrary. The same four rectangle vertices can appear in 24 different orders, and only some of them correspond to walking around the perimeter correctly.

The right-angle test uses the dot product:

$$\vec{u} \cdot \vec{v} = 0$$

which is the standard integer-safe orthogonality condition.

One subtle detail is rejecting zero-length sides. Without this check, repeated or degenerate points could accidentally satisfy the equal-side conditions. The problem guarantees distinct input points globally, but defensive geometry code should still verify positive lengths explicitly.

Another subtle point is using squared distances instead of actual Euclidean lengths. Comparing floating point square roots directly is unnecessary and less reliable.

Worked Examples

Example 1

Input:

The algorithm tries subsets until it reaches points 5, 6, 7, 8 as the square.

Square Candidate	Pairwise Distances	Square Valid	Rectangle Valid
1 2 3 4	mixed	No	not checked
5 6 7 8	1 1 1 1 2 2	Yes	Yes

The second group forms a unit square rotated by 45 degrees:

$$(1,1),(2,2),(2,1),(1,2)$$

The remaining four points form an axis-aligned rectangle.

This example shows why relying on axis alignment would fail. The square is rotated.

Example 2

Consider this input:

Square Candidate	Observation	Result
any 4 collinear points	zero area	rejected
mixed subsets	distances inconsistent	rejected

No partition creates both a square and a rectangle simultaneously.

The algorithm eventually exhausts all 70 subsets and prints "NO".

This example demonstrates why positive-area checks matter.

Complexity Analysis

Measure	Complexity	Explanation
Time	$O\left(\binom{8}{4} \cdot 24\right)$	70 subsets, each rectangle check tries at most 24 permutations
Space	$O(1)$	Only a few temporary arrays and vectors are stored

The total operation count is tiny. Even with several geometric checks per permutation, the runtime is comfortably below the limits.

Test Cases

# helper: run solution on input string, return output string
import sys
import io
from itertools import combinations, permutations

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)

    input = sys.stdin.readline

    def dist2(a, b):
        dx = a[0] - b[0]
        dy = a[1] - b[1]
        return dx * dx + dy * dy

    def is_square(points):
        dists = []

        for i in range(4):
            for j in range(i + 1, 4):
                dists.append(dist2(points[i], points[j]))

        dists.sort()

        if dists[0] == 0:
            return False

        return (
            dists[0] == dists[1] == dists[2] == dists[3]
            and dists[4] == dists[5]
            and dists[4] == 2 * dists[0]
        )

    def dot(ax, ay, bx, by):
        return ax * bx + ay * by

    def is_rectangle(points):
        for p in permutations(points):
            a, b, c, d = p

            abx = b[0] - a[0]
            aby = b[1] - a[1]

            bcx = c[0] - b[0]
            bcy = c[1] - b[1]

            if dot(abx, aby, bcx, bcy) != 0:
                continue

            if dist2(a, b) == 0 or dist2(b, c) == 0:
                continue

            if dist2(a, b) != dist2(c, d):
                continue

            if dist2(b, c) != dist2(d, a):
                continue

            return True

        return False

    pts = [tuple(map(int, input().split())) for _ in range(8)]

    indices = list(range(8))

    out = []

    for square_ids in combinations(indices, 4):
        sset = set(square_ids)

        rect_ids = [i for i in indices if i not in sset]

        sp = [pts[i] for i in square_ids]
        rp = [pts[i] for i in rect_ids]

        if is_square(sp) and is_rectangle(rp):
            out.append("YES")
            out.append(" ".join(str(i + 1) for i in square_ids))
            out.append(" ".join(str(i + 1) for i in rect_ids))
            return "\n".join(out)

    return "NO"

# provided sample
assert run(
"""0 0
10 11
10 0
0 11
1 1
2 2
2 1
1 2
"""
).startswith("YES")

# rotated square + rectangle
assert run(
"""0 0
1 1
2 0
1 -1
10 10
14 10
14 12
10 12
"""
).startswith("YES")

# impossible configuration
assert run(
"""0 0
1 0
2 0
3 0
0 1
1 1
2 1
3 1
"""
) == "NO"

# two squares, second used as rectangle
assert run(
"""0 0
1 0
1 1
0 1
10 10
12 10
12 12
10 12
"""
).startswith("YES")

# large coordinates
assert run(
"""10000 10000
10001 10000
10001 10001
10000 10001
-10000 -10000
-9990 -10000
-9990 -9995
-10000 -9995
"""
).startswith("YES")

Test input	Expected output	What it validates
Official sample	YES	Basic correctness
Rotated square	YES	Rotation handling
Collinear structure	NO	Degenerate rejection
Two squares	YES	Rectangle may also be square
Large coordinates	YES	Integer arithmetic safety

Edge Cases

A dangerous edge case is four collinear points masquerading as a rectangle.

Input:

When permutations are tested, every candidate ordering eventually fails the perpendicularity check:

$$\overrightarrow{AB} \cdot \overrightarrow{BC} \neq 0$$

because all vectors lie on the same line. The algorithm correctly rejects every partition and prints "NO".

Another tricky case is shuffled vertex order.

Input:

The square points are not given cyclically. A naive adjacent-side checker would fail immediately. Our solution instead computes all six pairwise distances:

$$1,1,1,1,2,2$$

which uniquely identifies a square regardless of ordering.

Rotated rectangles also require careful handling.

Input:

The first four points form a rotated rectangle. Since the rectangle validator uses vector dot products instead of axis comparisons, it correctly identifies the right angles even though no edges are horizontal or vertical.