CF 104790G - Geometry Game

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

Solution

Problem Understanding

We are given four points in the plane, already arranged in clockwise order, and guaranteed to form a strictly convex quadrilateral. Our task is to classify the shape formed by connecting these points in order and closing the cycle.

The classification is hierarchical. We must decide whether the quadrilateral is a square, rectangle, rhombus, parallelogram, trapezium, kite, or none, and always output the most specific one that fits. This means if a shape satisfies multiple definitions, we pick the most restrictive label in the given order.

The constraints are loose in terms of input size, since there is only a single quadrilateral per test case. This removes any need for preprocessing or asymptotic optimizations beyond constant time geometry computations. The real challenge is correctness in geometric classification under integer coordinates up to 10^9, which implies we must avoid floating point errors and rely on integer arithmetic such as squared distances and cross products.

A few edge situations matter even though the points are convex and ordered. The first is distinguishing between parallelogram and trapezium, since both depend on parallelism and a naive check might incorrectly count shared parallel structure twice. The second is distinguishing square, rectangle, and rhombus, since all are special cases of parallelograms with additional constraints. The third is kite detection, which is often misinterpreted as any quadrilateral with two equal adjacent sides, but must be carefully excluded when a stronger classification already applies.

For example, a square like (0,0), (0,1), (1,1), (1,0) should not be classified as kite even though it technically has multiple symmetry axes, because square is more restrictive.

Another subtle case is a general parallelogram that is not a rectangle or rhombus, such as (1,1), (2,3), (4,5), (3,3), where opposite sides are parallel but angles and lengths differ. A careless implementation that checks only side equality or only slopes will misclassify it.

Finally, trapezium detection must correctly identify exactly one pair of parallel sides, not at least one. A parallelogram has two such pairs and must not be counted as trapezium.

Approaches

A brute-force way to classify the quadrilateral is to explicitly test every definition directly from its geometric description. We could check all angle conditions using dot products, all side equalities using distances, and all parallelism conditions using cross products, then evaluate each shape rule one by one.

This works correctly because each property is checkable from first principles: equality of sides via squared distances, right angles via dot product zero, and parallelism via cross product zero. However, the naive structure tends to recompute the same quantities repeatedly and mixes floating angle reasoning if not careful. Even more importantly, a literal interpretation of each definition without normalization leads to redundant checks and fragile logic, especially for kite symmetry.

The key insight is that all required properties reduce to a small set of reusable primitives: squared edge lengths, dot products between adjacent edges, and cross products between opposite edges. Once we compute the four edge vectors, every classification condition becomes a combination of these primitives. This allows us to evaluate all shape types in constant time with consistent numerical stability.

Instead of thinking in terms of geometric definitions separately, we treat the quadrilateral as a cycle of vectors and derive all properties from that representation.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(1)	O(1)	Too slow in design, error prone
Optimal	O(1)	O(1)	Accepted

Algorithm Walkthrough

We label the points in order as A, B, C, D.

1. Compute edge vectors and squared side lengths

We form vectors AB, BC, CD, DA and compute their squared lengths. Squared lengths avoid floating point errors and are sufficient for equality comparisons.

2. Compute dot products for right angles

We compute AB · BC, BC · CD, CD · DA, and DA · AB. A dot product of zero indicates a right angle.

3. Compute cross products for parallelism

We compute AB × CD and BC × DA. A zero cross product indicates parallel lines.

4. Check square

We verify all sides are equal and all angles are right angles. This fully characterizes a square in a convex quadrilateral.

5. Check rectangle

We verify all angles are right angles. Side lengths do not need to be equal.

6. Check rhombus

We verify all four sides are equal. Angles are not constrained beyond convexity.

7. Check parallelogram

We verify both pairs of opposite sides are parallel.

8. Check trapezium

We verify exactly one pair of opposite sides is parallel. This requires XOR logic on the two parallel checks.

9. Check kite

We verify either AB equals BC and CD equals DA, or BC equals CD and DA equals AB. This encodes two pairs of adjacent equal sides.

10. Otherwise output none

Why it works

Every classification reduces to algebraic invariants of a quadrilateral under Euclidean geometry. Side equality is captured by squared distances, angle structure is captured by dot products, and parallel structure is captured by cross products. Since all conditions are evaluated on the same canonical representation, no geometric ambiguity remains. The hierarchy ensures that whenever multiple properties hold, the most restrictive one is selected first, preventing misclassification.

Python Solution

import sys
input = sys.stdin.readline

def sq_dist(x1, y1, x2, y2):
    dx = x1 - x2
    dy = y1 - y2
    return dx * dx + dy * dy

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

def cross(ax, ay, bx, by):
    return ax * by - ay * bx

x = []
y = []

for _ in range(4):
    xi, yi = map(int, input().split())
    x.append(xi)
    y.append(yi)

ax, ay = x[0], y[0]
bx, by = x[1], y[1]
cx, cy = x[2], y[2]
dx, dy = x[3], y[3]

AB = (bx - ax, by - ay)
BC = (cx - bx, cy - by)
CD = (dx - cx, dy - cy)
DA = (ax - dx, ay - dy)

s1 = sq_dist(ax, ay, bx, by)
s2 = sq_dist(bx, by, cx, cy)
s3 = sq_dist(cx, cy, dx, dy)
s4 = sq_dist(dx, dy, ax, ay)

right1 = dot(*AB, *BC) == 0
right2 = dot(*BC, *CD) == 0
right3 = dot(*CD, *DA) == 0
right4 = dot(*DA, *AB) == 0

par1 = cross(*AB, *CD) == 0
par2 = cross(*BC, *DA) == 0

if s1 == s2 == s3 == s4 and right1 and right2 and right3 and right4:
    print("square")
elif right1 and right2 and right3 and right4:
    print("rectangle")
elif s1 == s2 == s3 == s4:
    print("rhombus")
elif par1 and par2:
    print("parallelogram")
elif par1 ^ par2:
    print("trapezium")
else:
    kite1 = (s1 == s2 and s3 == s4)
    kite2 = (s2 == s3 and s4 == s1)
    if kite1 or kite2:
        print("kite")
    else:
        print("none")

The code first constructs edge vectors so that all geometric tests become simple arithmetic operations. Squared distances are used consistently to avoid precision issues. The ordering of checks follows the required hierarchy so that more specific shapes are detected before their generalizations.

A subtle implementation detail is the use of XOR for trapezium detection. Since a parallelogram would satisfy both parallel checks, XOR ensures it is excluded. Another key point is that kite detection is deferred until after all stronger classes are ruled out, preventing mislabeling of squares and rhombuses.

Worked Examples

Example 1

Input:

(0,0)
(0,1)
(1,1)
(1,0)

Step	s1	s2	s3	s4	right angles	parallels	decision
compute	1	1	1	1	pending	pending	square check
angles	true	true	true	true	all true	-	square

This confirms all sides equal and all angles right, so the algorithm selects square at the first matching condition.

Example 2

Input:

(1,1)
(2,3)
(4,5)
(3,3)

Step	s1	s2	s3	s4	right angles	parallels	decision
compute	diff	diff	diff	diff	some false	both true	parallelogram

Here opposite sides are parallel in both pairs, but angles are not right and sides are not equal, so it becomes a parallelogram.

The trace shows that classification depends only on structural invariants, not coordinate magnitudes.

Complexity Analysis

| Measure | Complexity | Explanation |

|---|---|---|---|

| Time | O(1) | Constant number of arithmetic operations on four points |

| Space | O(1) | Only a fixed number of variables for vectors and scalars |

The computation is purely local and independent of coordinate size, so it comfortably fits within any constraints.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    from collections import deque
    import math

    x = []
    y = []
    for _ in range(4):
        xi, yi = map(int, input().split())
        x.append(xi)
        y.append(yi)

    def sq(a,b,c,d):
        return (a-c)**2 + (b-d)**2
    def dot(ax,ay,bx,by):
        return ax*bx+ay*by
    def cross(ax,ay,bx,by):
        return ax*by-ay*bx

    ax,ay,bx,by,cx,cy,dx,dy = x[0],y[0],x[1],y[1],x[2],y[2],x[3],y[3]

    AB=(bx-ax,by-ay)
    BC=(cx-bx,cy-by)
    CD=(dx-cx,dy-cy)
    DA=(ax-dx,ay-dy)

    s1=sq(ax,ay,bx,by)
    s2=sq(bx,by,cx,cy)
    s3=sq(cx,cy,dx,dy)
    s4=sq(dx,dy,ax,ay)

    right1=dot(*AB,*BC)==0
    right2=dot(*BC,*CD)==0
    right3=dot(*CD,*DA)==0
    right4=dot(*DA,*AB)==0

    par1=cross(*AB,*CD)==0
    par2=cross(*BC,*DA)==0

    if s1==s2==s3==s4 and right1 and right2 and right3 and right4:
        return "square"
    elif right1 and right2 and right3 and right4:
        return "rectangle"
    elif s1==s2==s3==s4:
        return "rhombus"
    elif par1 and par2:
        return "parallelogram"
    elif par1 ^ par2:
        return "trapezium"
    else:
        kite1=(s1==s2 and s3==s4)
        kite2=(s2==s3 and s4==s1)
        return "kite" if (kite1 or kite2) else "none"

# provided sample
assert run("""0 0
0 1
1 1
1 0
""") == "square"

assert run("""1 1
2 3
4 5
3 3
""") == "parallelogram"

# custom cases
assert run("""0 0
1 0
2 0
1 1
""") in ["kite", "trapezium", "none"]

assert run("""0 0
2 0
3 1
1 1
""") in ["parallelogram", "trapezium"]

assert run("""0 0
1 1
2 0
1 -1
""") in ["rhombus", "kite", "parallelogram"]

Test input	Expected output	What it validates
square sample	square	full equality and right angle detection
parallelogram sample	parallelogram	opposite side parallelism
degenerate kite-like	variable	adjacency logic robustness
slanted quad	variable	parallel detection correctness
diamond shape	variable	rhombus vs kite ambiguity

Edge Cases

A key edge case is when the quadrilateral is a square. In that situation, it technically satisfies kite symmetry and rhombus properties as well, but the hierarchy forces square to be chosen first. The algorithm handles this because the square condition is checked before all others and requires both equal sides and right angles simultaneously.

Another edge case is a rhombus that is not a square. All sides are equal, but angles are not 90 degrees. The algorithm correctly skips the rectangle check because dot products are nonzero, and then classifies it as rhombus before reaching parallelogram.

A parallelogram that is not a rectangle or rhombus is handled purely through the cross product checks. Since both pairs of opposite sides are parallel, the XOR condition for trapezium is false and kite conditions fail due to lack of adjacent equal sides, so it correctly falls into parallelogram.

A trapezium case occurs when exactly one pair of opposite sides is parallel. The XOR condition ensures that a parallelogram does not accidentally qualify. This is the most common source of misclassification in naive implementations that only check “any parallel pair exists”.