Problem 2 - Shape Equivalence
Introduction
This problem requires you to determine if one shape can be transformed
into another by a 0-, 90-, 180-, or 270- degree rotation around
the origin followed by a translation.
The shapes to be considered for this problem are formed
by filling in unit squares centered on the lattice points
on a sheet of graph paper. The input is then a
list of the coordinates of the centers of the squares.
Input
The first line of input is a positive integer giving
the total area of the shapes.
The coordinates of the blocks that make up the first shape follow,
given as an x-coordinate followed by a y-coordinate. The x- and
y-coordinates will be integers and will be separated by a single space.
There will be
no other spaces on the line. After the coordinates for the first shape
come the coordinates for the second shape in the same format. There
is no limit on the size of the shapes or the values of the coordinates.
Each square in a shape will be listed only once.
Output
The output must be NO if the shapes are not equivalent
by a rotation followed by translation. If they are equivalent
then the output must be the angle of rotation in the clockwise
direction followed by the necessary translation given as the distance to
move in the x-direction followed by the distance to move in the y-direction.
This output must be on a single line with the numbers separated by
single spaces.
If more than one angle of rotation could work, the smallest nonnegative
angle should be output.
Example
The following shapes could be tested for equivalance with the input file
given below. Note that if you rotate the left shape 270 degrees and
then move it one square to the left and one square up
you get exactly the picture on the right.
Input:
4
-2 -1
-2 -2
-1 -1
0 -1
0 -1
0 0
1 -1
0 1
Output:
270 -1 1
