Similar Triangles

Interview

Time limit1sMemory limit1024 MB

Summary
Given two triangles by integer vertex coordinates, decide whether they are similar and if so print the squared similarity coefficient as a reduced fraction p/q, else print -1.
Level

Medium4 of 10

Topics
Geometry, Math, Sorting, Number theory
Solved
No attempts yet

Problem

Juku is studying triangle similarity at school. Two triangles are similar when all pairs of corresponding angles are equal and the corresponding side lengths are proportional. Two similar triangles may be rotated, reflected, and translated with respect to each other. The ratio of the corresponding side lengths of two similar triangles is called their similarity coefficient.

For homework Juku is given several pairs of triangles and must determine the similarity relationship of each pair. Help Juku by writing a program that decides whether two triangles are similar and, if so, reports their similarity coefficient.

Input

The first line contains six integers: the xx and yy coordinates of the three vertices of the first triangle, in the order x1 y1 x2 y2 x3 y3x_1\ y_1\ x_2\ y_2\ x_3\ y_3. Each coordinate lies between −109-10^9 and 10910^9. The second line contains six integers in the same format, giving the vertices of the second triangle. The vertices may be listed in either clockwise or counterclockwise order. The three given points always form a triangle (there are no coincident points and no three collinear points).

Output

Let kk be the similarity coefficient — how many times larger the first triangle is than the second (so k<1k < 1 if the first triangle is smaller). Because all vertex coordinates are integers, every squared side length is an integer, so k2k^2 is always a rational number (while kk itself may be irrational). If the two triangles are similar, print k2k^2 as a reduced fraction p/q with q≥1q \ge 1 and gcd⁡(p,q)=1\gcd(p, q) = 1; always print the denominator, even when it equals 11 (for example, 4/1). If the two triangles are not similar, print -1.

Examples4

  1. Example 1

    Input
    0 0 6 0 0 3
    -1 3 1 -1 -1 -1
    
    Expected output
    9/4
    
  2. Example 2

    Input
    0 0 3 0 1 1
    0 0 2 0 1 1
    
    Expected output
    -1
    
  3. Example 3

    Input
    0 0 1 0 0 1
    0 0 1 0 0 1
    
    Expected output
    1/1
    
  4. Example 4

    Input
    -1 3 1 -1 -1 -1
    0 0 6 0 0 3
    
    Expected output
    4/9