After analyzing the floor layout provided in the previous problem to determine the orientations of the tiles, you head over to the worksite to start drafting up the plan. However once you arrive you find that the work crew has already laid out the tiles in a regular pattern, without any regard to the plan!
The work crew has taken the initiative to lay out the tiles such that all tiles
of a similar orientation form one large rhombus.
Note that two tiles share a vertex at (0, 0).
After a quick discussion among the planning committee, it is decided that any rotation or reflection of the original design would also be acceptable. However the committee urges you to work quickly in order to complete the project before an upcoming holiday.
Observing the floor tiles, you find that they are recessed into the floor itself
and could not possibly be removed individually by hand, and then replaced into
another location. Instead the work crew has built an odd machine using a system of
levers and pulleys. This machine can lift a "group" of 3 closely-packed tiles and
rotate them by 60°. A group of 3 tiles counts as "closely-packed" if they all
share a vertex of internal angle 120°, thereby forming a small hexagon with the
group.
Here we see a pattern being corrected in 2 total moves.
Note that the end result is a rotation of the given pattern in the first example below.
The council impatiently asks - can you fix this mistake?
Problem Statement
Input Data
First line will be S. The side length of the bounding hexagon on the floor.
3 * S^2 lines will then follow, each with two space-separated values (x, y)
corresponding to the centerpoints of tile on the lattice described above.
Answer
Should consist of a single integer, corresponding to the minimum quantity of
"group rotations" required to alter the floor tile layout into some rotation or
reflection of the given layout.
Example
An example with S = 2:
input data:
2 0
8 -2
5 -3
11 3
7 1
13 -1
4 2
10 0
7 3
13 1
5 -1
11 -3
answer:
2
And here is a slightly larger example:
input data:
3
2 0
7 5
5 3
5 1
7 -5
17 -5
17 5
22 0
5 -1
5 -3
14 -4
14 4
11 5
11 -5
19 3
16 2
19 1
19 -3
19 -1
16 -2
9 3
9 1
12 2
14 0
9 -3
12 -2
9 -1
answer:
10