В казино Вована все крупье являются роботами. Однажды у Вована появилась мысль, что было бы полезно, если бы роботы, играющие в домино с клиентами, могли распознавать тип костяшки перед тем, как она перевёрнута, то есть, когда костяшка лежит на столе лицевой стороной вниз. К счастью, это возможно, поскольку точки на костяшках являются бриллиантами, а бриллианты можно увидеть с помощью рентгеновских лучей. Двигая манипулятор над костяшкой, робот может направить рентгеновские лучи через костяшку в камеру, расположенную в ноге робота. Используя полученное фото, специальная программа должна распознать тип костяшки. Теперь попробуйте угадать, кто напишет эту программу.
Костяшка является прямоугольником размером 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 (A ≤ B) — число точек в двух квадратах костяшки. Если возможно несколько ответов, они должны быть даны в лексикографическом порядке. Гарантируется, что ввод всегда корректен.
Пример
исходные данные | результат |
---|
2
1.12 2.2
7 -3.0001
| 0 2
1 1
|
Автор задачи: Екатерина Овечкина, Станислав Васильев
Источник задачи: Quarter-Final of XXXI ACM ICPC - Yekaterinburg - 2006