TopCoder

User's AC Ratio

NaN% (0/0)

Submission's AC Ratio

NaN% (0/0)

Tags

Description

    Patrick is a big fan of the bricks. He has been collecting the bricks of different colors, sizes,
and shapes, since he was little. Recently, he got a job in another city, and he planned to move next week. Since the new apartment is much smaller than the old one, Patrick decided to give away his bricks to the kids in his neighborhood. However, to receive the gift, the kid must play the bricks with Patrick and solve a brick game. The game is quite simple and the rules are as
follows:


1. The kid chooses a number N by casting lots.


2. Then, Patrick randomly selects N bricks from his collection.


3. The kid has to figure out the similar bricks from the N ones.


4. The kid will obtain the N bricks for free if he gives the correct answer.


    Note that the two bricks are considered similar if and only if their corresponding angles are all congruent and corresponding sides are all proportional with/without 180-degree flipping.

    For the ease of representation, we describe each brick by a sequence of vertices along the
border of the brick in clockwise order using the 2D Cartesian coordinate system. For instance, if N = 4, and the four bricks are B1 = {(4,1) (4,7) (8,7) (8,5) (6,5) (6,1)}, B2 = {(6,5) (6,3) (5,3) (5,4) (3,4) (3,5)}, B3 = {(10,1) (1,1) (1,4) (7,4) (7,7) (10,7)}, and B4 = {(6,3) (6,1) (4,1) (4,7) (8,7) (8,3)}. We know that B1 and B2 are similar, because their corresponding angles are all congruent and corresponding sides are all proportional. Moreover, B2 and B3 are similar, because, after flipping B3 , their corresponding angles are all congruent and corresponding sides
are all proportional. Meanwhile, B4 is not similar to any other bricks. Thus, we know the answer of this brick game is 3, and the three similar bricks are B1 , B2 , and B3 .

    For simplicity, we assume N is an integer, and 3 ≤ N ≤ 10. Each polygon is simple (i.e., the boundary of the polygon does not cross itself) and represented by a list of P vertices in clockwise order. P is an integer, and 3 ≤ P ≤ 10. The X, Y coordinates of the i-th vertex of the polygon is (Xi , Yi ). Xi and Yi are positive real numbers to four decimal places; moreover,
0 < Xi ≤ 1, 000 and 0 < Yi ≤ 1, 000. Finally, for each brick game, there is either none or only
one
set of bricks that are similar. In addition, all bricks in a game have the same number of vertices.


Input Format

There are multiple test cases in the input file. For each test case, the first line contains a positive
integer N representing the number of polygons in the case, and N = 0 indicates the end of the
test data. The second line contains a positive integer P , representing the number of vertices
contained by each polygon. In the following N lines, the i-th line contains 2P positive real
numbers to four decimal places, and they are separated by one single space. Specifically, the
(2k − 1)-th and (2k)-th real numbers in the i-th line represent the X and Y coordinate values
of the k-th vertex of the i-th brick respectively.

Output Format

Please output the answer of each test case in two lines. The first line contains an integer,
representing the number of similar bricks in the test case. The second line contains the sequence
numbers of the bricks that are similar in ascending order and separated by one single space. If
there are no similar bricks in the test case, please output 0 in both the first line and the second
line.

Sample Input 1

4
6
4.0000 1.0000 4.0000 7.0000 8.0000 7.0000 8.0000 5.0000 6.0000 5.0000 6.0000 1.0000
6.0000 5.0000 6.0000 3.0000 5.0000 3.0000 5.0000 4.0000 3.0000 4.0000 3.0000 5.0000
10.0000 1.0000 1.0000 1.0000 1.0000 4.0000 7.0000 4.0000 7.0000 7.0000 10.0000 7.0000
6.0000 3.0000 6.0000 1.0000 4.0000 1.0000 4.0000 7.0000 8.0000 7.0000 8.0000 3.0000
4
3
2.0000 1.0000 4.0000 4.0000 6.0000 1.0000
4.0000 7.0000 6.0000 9.0000 11.0000 1.0000
6.0000 9.0000 12.0000 6.0000 6.0000 6.0000
4.0000 13.0000 4.0000 1.0000 2.0000 7.0000
4
3
2.0000 1.0000 4.0000 4.0000 6.0000 1.0000
4.0000 7.0000 6.0000 9.0000 11.0000 1.0000
7.0000 2.0000 7.0000 6.0000 10.0000 4.0000
4.0000 13.0000 4.0000 1.0000 2.0000 7.0000
0

Sample Output 1

3
1 2 3
0
0
2
1 3

Hints

Problem Source

Migrated from old NTUJ.

The ACM-ICPC 2010 Asia Regional Contest, Site Kaohsiung

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 10000 65536 200