Canadian Computing Competition: 2013 Stage 2, Day 2, Problem 2
While travelling from Earth to Krypton, Superman was caught in a wormhole and transported instantly to some unknown location. Superman remembers seeing periodic comets from Earth, and he can see some periodic comets from his current location. He would like to use these comets to find his bearings, but first he has to match up which one is which.
The specific comets Superman sees are periodic Gaussian hyper-comets. A periodic Gaussian hyper-comet is a sequence (
Superman was disoriented in both space and time. In terms of space this means a comet that he saw before might now have its whole set of points rotated, both axes scaled by the same positive factor, and/or translated. Furthermore, since he was disoriented in time, the first point of a comet he used to know might not be the first point anymore.
For example, the right-triangular hyper-comet
Your goal is: given a periodic sequence of points corresponding to a Gaussian hyper-comet Superman saw from Earth, and a Gaussian hyper-comet Superman sees now, determine if they could be the same comet.
Input Specification
The first line contains
Each test case begins with an integer
It is guaranteed that all of the coordinates are integers between
Output Specification
For each test case, if the two sequences could represent the same hyper-comet under this disorientation process, print out the smallest positive integer
Sample Input
3
3
0 0
1 0
0 1
20 20
60 20
40 40
4
0 0
1 1
0 0
1 1
30 30
19 23
30 30
19 23
4
0 0
1 0
1 1
0 1
0 0
2 0
2 1
0 1
Sample Output
3
1
0
Comments