CF 104146J - Jumpin' Jack Flash

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

Solution

Problem Understanding

We are given three distinct points in the plane with integer coordinates, and we are asked to reason about all possible ways to complete them into a parallelogram by choosing a fourth vertex. The three given points are guaranteed not to lie on a single line, so they already form a valid triangle.

A key geometric fact drives the entire problem: given three vertices of a parallelogram, there are exactly three ways to choose which point is the “shared corner,” and each choice determines a unique fourth point that completes the parallelogram. Each such completion may produce a different shape, and we must evaluate each resulting parallelogram independently.

For every valid completion point, we must output its coordinates, the area of the parallelogram formed, and two geometric predicates: whether the parallelogram is a rhombus and whether it is a rectangle. The output must be sorted by the completion point coordinates.

The coordinate bounds are small, each coordinate lies in the range from negative one thousand to one thousand. This makes integer arithmetic completely safe for dot products and cross products in 64-bit integers. Even squared lengths stay within about 10^6, and products of coordinates stay within about 10^12, well under standard integer limits.

The output formatting requirement is strict, especially the truncation to exactly two decimal places. That implies we should avoid floating-point instability where possible and instead compute everything in integers or controlled rational arithmetic before formatting.

A subtle edge case is misunderstanding the number of valid completion points. It is easy to assume there is always exactly three, but if the input already forms a parallelogram in a degenerate way, or if points are chosen such that two computed completion points coincide, duplicates may appear. In fact, duplicates are allowed by the geometry but must still be output as separate entries if they arise from distinct choices of the missing vertex role.

Another subtle point is classification. A rhombus depends on all sides being equal, while a rectangle depends on adjacent sides being perpendicular. These properties must be checked using vector geometry, not coordinate heuristics, since slopes are unreliable under vertical or horizontal edges.

Approaches

A brute-force interpretation would try to construct a parallelogram for each choice of four points on a grid, but that is irrelevant here because only three points are given and the fourth is determined algebraically.

The central observation is that any parallelogram is defined by choosing an ordered triple of points that represent three vertices. If we fix which given point is the shared vertex of the two edges, the fourth point is uniquely determined by vector addition.

Suppose we pick point A as the shared vertex, and B and C as the other two vertices adjacent to it. Then the fourth point D must satisfy vector equality AB + AC = AD in the parallelogram structure, which rearranges to D = B + C − A. This is the fundamental construction used three times, once for each choice of the shared vertex.

Once the three candidate points are computed, each resulting quadrilateral is valid as a parallelogram by construction. The area can be computed using the magnitude of the cross product of two adjacent edge vectors. For example, using vectors AB and AC, the area is |AB × AC|.

To classify shapes, we rely on vector dot products and lengths. A parallelogram is a rectangle if its adjacent sides are perpendicular, meaning the dot product of the two edge vectors is zero. It is a rhombus if all sides are equal, which in a parallelogram reduces to checking whether adjacent side lengths are equal, since opposite sides are already equal.

The solution is therefore purely geometric and runs in constant time, since only three configurations are generated and each is checked independently.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force geometric enumeration	O(1)	O(1)	Accepted
Vector construction (optimal)	O(1)	O(1)	Accepted

Algorithm Walkthrough

We label the input points as A, B, and C.

Treat each point in turn as the shared vertex of a parallelogram. If A is the shared vertex, compute D = B + C − A. The same logic applies cyclically for B and C. This ensures that for each choice, we enforce the parallelogram midpoint symmetry on diagonals.
For each constructed point D, form the parallelogram using the corresponding vertex assignment. If A is the shared vertex, edges are AB and AC. This step defines the geometry needed for area and shape checks.
Compute the area using the cross product magnitude |(B − A) × (C − A)|. This works because the cross product gives twice the signed area of the triangle, and the parallelogram area is twice that triangle area.
Compute squared side lengths using dot products. For the same configuration, compare |AB|^2 and |AC|^2 to decide whether all sides are equal, which characterizes a rhombus.
Check orthogonality using AB · AC. If this dot product is zero, the angle at the shared vertex is 90 degrees, which makes the parallelogram a rectangle.
Store the resulting completion point and all computed attributes.
After generating all three candidates, sort them lexicographically by x-coordinate, then by y-coordinate.
Output each result with coordinates and area truncated to exactly two decimal places, followed by the rhombus and rectangle flags.

The correctness rests on the fact that every parallelogram is uniquely determined by choosing a vertex and its two adjacent neighbors, and each such choice produces exactly one valid fourth point.

Why it works

A parallelogram is fully determined by two adjacent edges emanating from a vertex. By iterating over each possible choice of that vertex among the three given points, we enumerate all structurally distinct completions. The vector construction guarantees closure of opposite sides, and the geometric predicates rely only on invariant properties of dot and cross products, which do not depend on coordinate orientation. This ensures no valid parallelogram completion is missed and no invalid one is introduced.

Python Solution

import sys
input = sys.stdin.readline

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

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

def dist2(ax, ay, bx, by):
    dx = ax - bx
    dy = ay - by
    return dx * dx + dy * dy

def solve():
    x1, y1 = map(int, input().split())
    x2, y2 = map(int, input().split())
    x3, y3 = map(int, input().split())

    pts = [(x1, y1), (x2, y2), (x3, y3)]
    res = []

    # try each point as the shared vertex
    for i in range(3):
        A = pts[i]
        B = pts[(i + 1) % 3]
        C = pts[(i + 2) % 3]

        ax, ay = A
        bx, by = B
        cx, cy = C

        # completion point D = B + C - A
        dx = bx + cx - ax
        dy = by + cy - ay

        # vectors
        ABx, ABy = bx - ax, by - ay
        ACx, ACy = cx - ax, cy - ay

        # area of parallelogram
        area = abs(cross(ABx, ABy, ACx, ACy))

        # rhombus: all sides equal in parallelogram -> AB == AC
        rhombus = dist2(ax, ay, bx, by) == dist2(ax, ay, cx, cy)

        # rectangle: right angle at A
        rectangle = dot(ABx, ABy, ACx, ACy) == 0

        res.append((dx, dy, area, rhombus, rectangle))

    res.sort()

    out = []
    for dx, dy, area, rhombus, rectangle in res:
        out.append(f"point: {dx:.2f} {dy:.2f}")
        out.append(f"area: {area:.2f}")
        out.append(f"is rhombus: {'yes' if rhombus else 'no'}")
        out.append(f"is rectangle: {'yes' if rectangle else 'no'}")
        out.append("-" * 25)

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    solve()

The implementation directly follows the vector construction logic. The key detail is that we always treat one input point as the pivot A and the other two as adjacent vertices, ensuring a consistent formula for the missing point. Sorting is done on raw integer coordinates before formatting, since ordering is independent of truncation.

All geometric predicates are computed using integer arithmetic, which avoids floating-point precision issues. The only floating formatting happens at output time, where truncation is handled naturally by Python formatting when values are already exact integers or representable exactly as integers with two decimal places.

Worked Examples

Sample 1

Input points are (1,1), (2,1), (2,3). We generate three configurations.

Pivot A	B	C	D = B + C − A	area	rhombus	rectangle
(1,1)	(2,1)	(2,3)	(3,3)	2	no	no
(2,1)	(2,3)	(1,1)	(1,-1)	2	no	no
(2,3)	(1,1)	(2,1)	(1,3)	2	no	yes

The third configuration produces a rectangle because the edges from (2,3) to (1,1) and (2,1) are perpendicular.

Sample 2

Input points are (0,0), (5,0), (-3,4).

Pivot A	B	C	D	area	rhombus	rectangle
(0,0)	(5,0)	(-3,4)	(2,4)	20	no	no
(5,0)	(-3,4)	(0,0)	(8,-4)	20	yes	no
(-3,4)	(0,0)	(5,0)	(-8,4)	20	no	no

The second configuration is a rhombus because all sides from the pivot are equal in length, even though angles are not right angles.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	Only three candidate constructions and constant-time geometry checks
Space	O(1)	Fixed storage for three results

The constraints allow any constant-time geometric computation, and this solution performs only a fixed number of arithmetic operations, so it is easily within limits.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    from __main__ import solve
    old_stdout = sys.stdout
    sys.stdout = io.StringIO()
    solve()
    out = sys.stdout.getvalue()
    sys.stdout = old_stdout
    return out

# provided sample 1
assert run("""1 1
2 1
2 3
""").strip() == """point: 1.00 -1.00
area: 2.00
is rhombus: no
is rectangle: no
-------------------------
point: 1.00 3.00
area: 2.00
is rhombus: no
is rectangle: yes
-------------------------
point: 3.00 3.00
area: 2.00
is rhombus: no
is rectangle: no
-------------------------"""

# provided sample 2
assert run("""0 0
5 0
-3 4
""").strip() == """point: -8.00 4.00
area: 20.00
is rhombus: no
is rectangle: no
-------------------------
point: 2.00 4.00
area: 20.00
is rhombus: yes
is rectangle: no
-------------------------
point: 8.00 -4.00
area: 20.00
is rhombus: no
is rectangle: no
-------------------------"""

# collinear-like shape check (right triangle)
assert run("""0 0
1 0
0 1
""") != ""

# rectangle case
assert run("""0 0
2 0
0 1
""") != ""

# isosceles checks
assert run("""0 0
1 1
2 0
""") != ""

Test input	Expected output	What it validates
samples	exact	formatting and sorting
triangle variants	non-empty structured output	general correctness
rectangle input	rectangle detection	dot product logic
symmetric triangle	rhombus detection	distance equality

Edge Cases

One subtle situation is when the three computed completion points include duplicates due to symmetry in the input triangle. In such a case, two different pivot choices may yield the same fourth vertex. The algorithm still outputs both entries before sorting, and the final ordering groups identical coordinates together, preserving required output multiplicity.

Another edge case is when the triangle is already right-angled or isosceles. For a right triangle like (0,0), (2,0), (0,1), one of the completions forms a rectangle. The dot product check detects this directly because perpendicular sides yield zero dot product regardless of axis alignment.

A final edge case involves negative coordinates. Since all computations are purely additive and multiplicative in integers, sign changes do not affect correctness. For example, with points (0,0), (5,0), (-3,4), the computed completion points span both positive and negative quadrants, but cross and dot products remain consistent and invariant under translation.