Want to try solving this problem? You can submit your code online if you log in or register.

**Input File:** `jigin.txt`

**Output File:** `jigout.txt`

**Time Limit:** 1 second

For your birthday, your friends pooled their pocket money together to buy you a rather unusual jigsaw puzzle. The pieces of this puzzle come in a variety of shapes. Every corner of every shape is a 90 degree angle, so in theory this should be an easy puzzle. However, to make it more difficult to match the pieces together, there are pictures on both sides of each piece!

After playing with the jigsaw puzzle for some time, it becomes clear to you that many of the pieces can fit into the same spot in the puzzle in more than one way. Simply by turning a piece around or flipping it over, you can fit it in exactly the same place but show a different or rotated picture.

For example, the first puzzle piece in the diagram below has two ways in which it can be flipped in order to retain the exact same shape and position (you can flip it about either a horizontal axis or a vertical axis, as indicated by the dotted lines). Furthermore, rotating the piece by 180 degrees about its centre will also preserve the shape and position. On the other hand, the second puzzle piece in the diagram has only one flip that will retain the same shape and position, and no rotations.

In order to make this jigsaw a little less difficult, your task is to determine all the possible ways in which you can rotate or flip a given jigsaw piece without altering its shape and position.

The input will describe a single jigsaw piece by listing the
the *x* and *y* coordinates of its corner points. The corners
will be listed in order around the border of the piece.
Each corner will be a 90 degree angle, and the line joining any two
adjacent corners will always be horizontal or vertical (this includes
the line joining the first and last corners in the list).

More precisely, the first line of input
will contain a single integer *n* representing the number of corners
(4 <= *n* <= 50,000).
Following this will be *n* lines each
describing a single corner point.
Each of these lines will contain two
integers *x* and *y* separated by a space, representing the
*x* and *y* coordinates of the corner point. You are guaranteed that
0 <= *x*,*y* <= 1,000,000.

For 80% of the available marks, the judges' test cases will use
*n* <= 1000.

The first line of output should contain a single integer listing the number of ways the jigsaw piece can be flipped or rotated without changing its shape and position.

Following this, you should describe each of these flips and rotations
in detail.
Specifically, each flip or rotation must be written as a
sequence of corner points, where the *i*th point in the sequence shows
where the *i*th point from the input has moved to.
As before, each point must appear on its own line, with
the *x* and *y* coordinates separated by a single space.

There should be a blank line separating different output sequences (i.e., different flips or rotations). Trailing newlines at the end of the file will be ignored (i.e., you will not lose marks if you have them).

The order in which you list the different flips and rotations does not matter (though the order in which you list the individual corner points for each output sequence is very important).

12 0 0 10 0 10 30 20 30 20 0 30 0 30 70 20 70 20 40 10 40 10 70 0 70

3 30 70 20 70 20 40 10 40 10 70 0 70 0 0 10 0 10 30 20 30 20 0 30 0 30 0 20 0 20 30 10 30 10 0 0 0 0 70 10 70 10 40 20 40 20 70 30 70 0 70 10 70 10 40 20 40 20 70 30 70 30 0 20 0 20 30 10 30 10 0 0 0

In the example above, there are three ways this shape can be rotated or flipped. The first describes a rotation by 180 degrees. We see from the first output sequence that the first input corner (0, 0) moves to (30, 70), the second input corner (10, 0) moves to (20, 70) and so on.

The second output sequence describes a flip about the vertical axis. Here the first input corner (0, 0) moves to (30, 0), the second input corner (10, 0) moves to (20, 0) and so on. Finally, the third output sequence describes a flip about the horizontal axis.

The score for each input file will be 100% if a correct solution is written to the output file and 0% otherwise.

Privacy
statement

© Australian Mathematics Trust 2001-2021

Page generated: 1 December 2021, 11:24am AEDT