PROBLEM STATEMENT
Implement a class Triangles with a method compare to determine how similar two
triangles are. Triangles can be either identical, identical after flipping,
identical after scaling, identical after flipping and scaling, or dissimilar.
(For a pictorial summary of the following examples, refer to
http://www.topcoder.com/contest/Triangles.html)
Two triangles are considered identical if one can be rotated and moved (but not
flipped or scaled) to match the other triangle. Another way to interpret what
it means to be identical is that the sides of each triangle are the same
lengths when advancing clockwise around each triangle. "0,0 4,0 4,3" and "5,4
8,0 8,4" is an example of two identical triangles.
Flipping is the act of reflecting one vertex of a triangle across the line
defined by the other points. Another way to interpret flipping is that two
triangles are identical after flipping if their sides are the same lengths when
advancing clockwise around one triangle and counter-clockwise around the other
triangle. "0,0 4,0 4,3" and "9,0 9,4 12,4" is an example of two triangles that
are identical after flipping.
Two triangles are identical after scaling if when otherwise compared, the sides
differ by a common factor. Thus, if one triangle has sides that are 2.5 times
the length of another, the triangles are identical after scaling. Note: the
lengths must also match clockwise to clockwise, otherwise flipping is also
required for identicality. "0,0 4,0 4,3" and "11,8 17,0 17,8" is an example of
two triangles that are identical after scaling. "0,0 4,0 4,3" and "18,0 18,8
24,8" is an example of two triangles that are identical after scaling and
flipping.
DEFINITION
Class Name: Triangles
Method Name: compare
Parameters: int[], int[]
Returns: int
Method signature (be sure your method is public): int compare(int[] triangleA,
int[] triangleB);
TopCoder will ensure the following:
* triangleA and triangleB contain exactly six elements each, corresponding to
the three vertices of each triangle [x1, y1, x2, y2, x3, y3].
* All values will be between -50 and 50, inclusive.
* All vertices will be unique.
* The triangle will never be 180-0-0 (flat).
Return value, in order of priority (4 takes priority over 3, etc.):
4 - Triangles are identical. Scaling and flips are not allowed.
3 - Triangles are not identical, but are identical after flipping. No scaling
is allowed.
2 - Triangles are identical after scaling all sides by some factor (other than
one). Flips are not allowed.
1 - Triangles are identical after scaling all sides by some factor (other than
one), but flipping is also required.
0 - Any other case
Note:
* Rotation by any angle is allowed in all cases
* Rotations can be of any measure (not just 90 degrees)
* The order of points in each triangle does not matter, so the first point of
triangleA does not need to match up with the first point of the triangleB.
EXAMPLES
- {0,0,4,0,4,3} and {5,4,8,0,8,4}, compare should return 4
- {0,0,4,0,4,3} and {9,0,9,4,12,4}, compare should return 3
- {0,0,4,0,4,3} and {11,8,17,0,17,8}, compare should return 2
- {0,0,4,0,4,3} and {18,0,18,8,24,8}, compare should return 1
- {0,0,4,0,4,3} and {0,0,4,0,4,4}, compare should return 0