AIOC Banner

Problem: Jigsaw

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


Jigsaw

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.

Input

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.

Output

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 ith point in the sequence shows where the ith 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).

Sample Input

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

Sample Output

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

Explanation

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.

Scoring

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

Contact: training@orac.amt.edu.au
Page generated: 29 March 2024,  4:56am AEDT