ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

MSU SE and Ural SU contest. Petrozavodsk training camp. Summer 2005

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

D. Проекты цветника

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
В конкурсе на лучший проект цветника приняло участие N человек. Каждый из них предоставил свой проект — конечную последовательность точек на плоскости, в которых планируется посадить по цветку. Чтобы избежать ненужной работы основной комисcии по рассмотрению одинаковых проектов, предварительная комиcсия хочет найти проекты, которые отличаются друг от друга перестановкой точек и их аффинным преобразованием, не меняющим ориентацию (радиус-вектор каждой точки умножается на матрицу с положительным определителем и складывается с некоторым фиксированным вектором).

Исходные данные

В первой строке записано число участников N (N ≤ 10000). Далее следует N описаний проектов. Каждое описание проекта начинается с длины после­дова­тельности M. Далее на следующих M строчках записаны координаты точек после­дова­тельности — пары целых чисел, не превосходящих по модулю 1000. Сумма длин всех после­дова­тельностей не превосходит 200000.

Результат

В первой строке вывести количество классов эквивалентности проектов. В следующих строчках вывести сами классы эквивалентности: после­дова­тельность номеров проектов (нумерация начинается с 1), в конце после­дова­тельности вывести 0.

Пример

исходные данныерезультат
7
5
1 2
0 0
6 0
0 4
2 7
5
1 2
3 9
0 1
2 3
9 2
5
-43 -37
-73 -47
-3 3
-23 -7
-3 63
3
0 0
1 0
0 1
3
0 0
1 0
3 0
3
10 3
3 7
5 2
3
6 1
6 5
6 7
4
4 6 0
5 7 0
1 3 0
2 0
Автор задачи: Андрей Румянцев
Источник задачи: Petrozavodsk summer training camp, August 2005.
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1383. Проекты цветника