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

NEERC, Восточный подрегион, Екатеринбург, октябрь 2006

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

J. Распознавание домино

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
В казино Вована все крупье являются роботами. Однажды у Вована появилась мысль, что было бы полезно, если бы роботы, играющие в домино с клиентами, могли распознавать тип костяшки перед тем, как она перевёрнута, то есть, когда костяшка лежит на столе лицевой стороной вниз. К счастью, это возможно, поскольку точки на костяшках являются бриллиантами, а бриллианты можно увидеть с помощью рентгеновских лучей. Двигая манипулятор над костяшкой, робот может направить рентгеновские лучи через костяшку в камеру, расположенную в ноге робота. Используя полученное фото, специальная программа должна распознать тип костяшки. Теперь попробуйте угадать, кто напишет эту программу.
Костяшка является прямоугольником размером L × 2L (1 ≤ L ≤ 100), состоящим из двух квадратов. В каждом из квадратов содержится от 0 до 6 точек, расположенных классическим способом. Чтобы описать расположение точек на квадрате, рассмотрим меньший квадрат с тем же центром, чьи стороны в два раза короче, чем стороны большего квадрата, и параллельны им.
1 точка находится в центре квадрата
2 точки расположены в левом нижнем и правом верхнем углах меньшего квадрата (если расположить костяшку вертикально)
3 точки расположены как 2 точки плюс точка в центре квадрата
4 точки находятся в четырёх углах меньшего квадрата
5 точек расположены как 4 точки плюс точка в центре квадрата
6 точек: 4 точки находятся в углах меньшего квадрата, а две точки находятся в середине тех сторон меньшего квадрата, которые параллельны длинным сторонам костяшки.
Ваша задача — проанализировать фотографию костяшки. Известно, что фото показывает все точки ровно одной костяшки. Плоскость приёмника камеры параллельна плоскости стола, нет перспективных или других искажений, но костяшка может быть произвольно повёрнута в плоскости стола. Не забудьте, что костяшка на столе перевёрнута.

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

Первая строка содержит N (1 ≤ N ≤ 12) — число точек, видимых на фото. Следующие N строк содержат координаты этих точек. Координаты точны до 0.0001. Координаты по модулю не превосходят 2000. Фото показывает реальный размер костяшки.

Результат

Выведите целые числа A и B (AB) — число точек в двух квадратах костяшки. Если возможно несколько ответов, они должны быть даны в лексикографическом порядке. Гарантируется, что ввод всегда корректен.

Пример

исходные данныерезультат
2
1.12 2.2
7 -3.0001
0 2
1 1
Автор задачи: Екатерина Овечкина, Станислав Васильев
Источник задачи: Quarter-Final of XXXI ACM ICPC - Yekaterinburg - 2006
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1509. Распознавание домино