### 2013 Canadian Computing Competition, Stage 2

## Day 2, Problem 2: Transforming Comets

While traveling 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 (`p`_{1},
`p`_{2}, ..., `p _{n}`) where each

`p`is a 2-dimensional point (

_{i}`x`,

_{i}`y`) with integer coordinates. The comet visits some point

_{i}`p`and then it visits point

_{i}`p`

_{i+1}. The sequence is periodic: after visiting

`p`the comet visits

_{n}`p`

_{1}, next (so the indices are interpreted modulo

`n`), Gaussian hyper-comets also have the special property that

`p`≠

_{i}`p`

_{i+1}for each i and

`p`

_{1}≠

`p`.

_{n}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 any more.

For example, the right-triangular hyper-comet ((0, 0), (1, 0),
(0, 1)) from earth might look like ((40, 40), (20, 20),
(60, 20)) or ((20, 20), (60, 20), (40, 40)). Note that
reversing time or space is not an allowed transformation, e.g. it's
**not** possible for this hyper-comet to appear as ((0, 1),
(1, 0), (0, 0)).

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

The first line contains 1 ≤ `t` ≤ 10, the
number of test cases to follow.

Each test case begins with an integer `n` where
2 ≤ `n` ≤ 500000. The following `n`
lines, for `i` from 1 to `n`, each contain a space-separated
pair of integers `x _{i}`

`y`. These lines denote the points for a sequence viewed from Earth. Then, similarly, there are

_{i}`n`more lines each containing a pair of integers

`x`′

_{i}`y`′; these lines denote the points for a sequence viewed Superman's current location.

_{i}It is guaranteed that all of the coordinates are integers between 0 and 30000 (inclusive).

### Output

For each test case, if the two sequences could represent the same
hyper-comet under this disorientation process, print out the smallest positive
integer `s` so that
`x`_{1} `y`_{1} could correspond
`x _{s}`′

`y`′. If there is no such

_{s}`s`, print 0.

### 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

All Submissions

Best Solutions

**Point Value:** 25 (partial)

**Time Limit:** 10.00s

**Memory Limit:** 128M

**Added:** May 19, 2013

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

nullptron Feb 08, 2014 - 9:13:39 pm UTC Wrong answer?SourSpinachon Feb 10, 2014 - 2:57:40 am UTC Re: Wrong answer?nullptron Feb 10, 2014 - 3:09:02 am UTC Re: Wrong answer?SourSpinachon Feb 10, 2014 - 2:48:37 pm UTC Re: Wrong answer?nullptron Feb 10, 2014 - 6:21:29 pm UTC Re: Wrong answer?