eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Earthquake Emendations

Earthquake Emendations

Лимит времени 0.1 секунд
Лимит использования памяти 64 MiB

A major earthquake has turned a beautiful stained glass window at the Farm Hill College chapel into shards of glass lying on the floor. The chapel manager is calling upon you to help him quickly put the window back together. Luckily the window only broke along its lead joints, and the individual colored pieces are all intact. Additionally, as if by divine intervention, all of the pieces landed on the floor either in their original orientation, or rotated by a multiple of 90 degrees (pi/2 radians), and no pieces have been flipped on their face. After much searching, a schematic of the original stained glass window as it stood before the earthquake was found in the library. You learn from the schematic that no two colored pieces of the window are identical in shape and size. With this schematic in hand, your mission is to write a program that will identify the strewn shards to help reassemble the window. Input Your program will be given several test cases, each comprising a description of a broken window for you to reassemble. Every test case begins with a single line containing an integer n (1n20), the number of individual glass pieces in the window. The next n lines each contain a description of a unique colored glass piece in the form of a simple polygon with nonzero area. The coordinates of the k (3k100) vertices of each polygon will be given in counter-clockwise order in the following format: x_1y_1x_2y_2 ... x_kykx_1y_1. You may assume that the vertices of each polygon are distinct, i.e., (x_i, y_i) <> (x_j, y_j) whenever i <> j, and consecutive vertices are not collinear. All coordinates are integers restricted to the range 0x_i, y_i100. The final line of each test case is the schematic of the original window, written as a concatenation of n non-overlapping polygons in the same format described above. Each of the polygons in the schematic is guaranteed to correspond to some rotation plus translation of one of the glass pieces described above. Test cases will be separated by blank lines, and the final line of the input will contain a single integer "0", marking the end of input. Output Your program should produce a single line of output for each test case. For every glass piece in the input for a test case, write a single integer indicating the position within the schematic that the piece appears. Separate the numbers with a single space in the output.

Пример

Входные данные #1
2
1 3 4 3 1 5 1 3
4 4 4 7 2 7 4 4
0 0 2 0 2 3 0 0 2 0 4 0 2 3 2 0

4
0 0 4 0 4 2 2 2 0 0
0 0 4 0 2 2 0 2 0 0
4 4 0 4 2 3 4 4
0 4 4 4 2 6 0 4
0 0 4 0 2 2 0 0 0 0 2 2 2 4 0 4 0 0 2 2 4 0 4 4 2 4 2 2 0 4 4 4 2 5 0 4

0
Выходные данные #1
1 2
3 2 4 1