Affine Mess

Time limit2sMemory limit128 MB

Summary
Given three integer start points and three integer end points, decide whether a snapped integer rotation, integer scaling, and integer translation map one set onto the other, and if so whether all such maps agree on the whole plane.
Level

Hard9 of 10

Topics
Geometry, Math, Brute force, Implementation
Solved
No attempts yet

Problem

A drawing program has a "snap to grid" feature that forces every control point to jump to the nearest grid point (the nearest point with integer coordinates). Three identical marker dots were placed on the drawing, and each landed on a grid point, so their coordinates are integers.

The drawing was then altered by three tools, and afterwards the three dots were still present, moved to new integer grid locations. The three tools were a rotation about the origin, a scaling about the origin, and a translation. The rotation was applied first; the scaling and the translation were applied after it in an unknown order (so the sequence was either rotation, translation, scaling or rotation, scaling, translation). The remembered constraints are:

  • Scaling: the x- and y-scaling factors were (possibly negative) nonzero integers, and the center of scaling was the origin (0,0)(0,0).
  • Translation: the x- and y-translation amounts were integers.
  • Rotation: it was specified by a point with integer coordinates (x,y)(x, y) on the perimeter of a square of width 2020 centered at the origin (hence −10≤x,y≤10-10 \le x, y \le 10, and ∣x∣|x| or ∣y∣|y| or both equal 1010). The drawing was rotated about the origin so that afterwards the positive x-axis passes through (x,y)(x, y).

Snapping to the nearest grid point took place immediately after the rotation; a coordinate whose fractional part is exactly 0.50.5 was rounded away from zero. Scaling by integer factors and translating by integer amounts keep integer coordinates integer, so no further snapping is needed.

Given the three original integer positions of the dots and their three final integer positions, decide whether the sequence of alterations can be reconstructed.

Input

The input contains several test cases. Each test case consists of six integer pairs (xi,yi)(x_i, y_i) with −500≤xi,yi≤500-500 \le x_i, y_i \le 500 for 1≤i≤61 \le i \le 6, written as three pairs per line over two lines. The first three pairs are the distinct initial locations of the three dots; the last three pairs are the distinct final locations. The order of the three pairs within each group is not significant: any initial dot may correspond to any of the three final locations.

The input ends with a line of six zeros, which is not a test case.

Output

For each test case, display its case number followed by exactly one of the following three messages:

  • equivalent solutions if one or more valid transformations exist and all of them have the same effect on the whole drawing (no matter what the whole drawing looks like).
  • inconsistent solutions if several valid transformations exist but in general they do not all map the entire drawing the same way (some drawing is mapped differently by two valid transformations).
  • no solution if neither of the first two situations occurs.

A valid transformation is a combination of a rotation, a translation, and a scaling (in the order rotation, translation, scaling or rotation, scaling, translation) that obeys the restrictions above and maps the initial set of three dots onto the final set, occupying all three final locations. Use the format Case X: <message>.

Examples3

  1. Example 1

    Input
    3 0 4 0 1 4
    -2 -4 -1 3 3 -4
    0 1 1 1 2 1
    1 2 2 2 3 2
    1 0 2 0 3 0
    3 3 1 1 2 2
    1 0 2 0 3 0
    3 2 1 1 2 2
    2 3 0 6 1 2
    2 3 0 6 1 2
    0 0 0 0 0 0
    
    Expected output
    Case 1: equivalent solutions
    Case 2: inconsistent solutions
    Case 3: no solution
    Case 4: inconsistent solutions
    Case 5: equivalent solutions
    
  2. Example 2

    Input
    3 0 4 0 1 4
    -2 -4 -1 3 3 -4
    0 0 0 0 0 0
    
    Expected output
    Case 1: equivalent solutions
    
  3. Example 3

    Input
    1 0 2 0 3 0
    3 3 1 1 2 2
    0 0 0 0 0 0
    
    Expected output
    Case 1: no solution