Задача 7. Две окружности ≡

Автор:Центральная предметно-методическая комиссия по информатике   Ограничение времени:2 сек
Входной файл:circles.in   Ограничение памяти:256 Мб
Выходной файл:circles.out  
Максимальный балл:100  

Условие

Юный футболист Митя обнаружил на школьном футбольном поле две различные окружности, нарисованные едва заметной белой краской. Вспомнив истории о загадочных кругах на полях, он отметил эти окружности с помощью небольших камушков. Митя разложил на поле n камушков так, чтобы каждый из них находился на одной из окружностей или даже на их пересечении, если эти окружности пересекаются. Получилось так, что на каждой окружности размещался хотя бы один камушек. Обладая отличным глазомером, Митя расположил камушки на окружностях абсолютно точно, без какой-либо погрешности.

На следующий день пошел дождь, краска стерлась, и нарисованные окружности исчезли, но все камушки остались на своих местах. Теперь Мите очень нужно найти доказательство необычного явления, свидетелем которого он был, то есть, восстановить окружности.

Требуется написать программу, которая по координатам камушков на поле находит вариант размещения их на двух несовпадающих окружностях.

Пояснения к примерам

В первом примере одна из искомых окружностей имеет центр в точке с координатами (1, 0), а вторая — в точке с координатами (3, 0). Обе окружности имеют радиус равный 1. Во втором примере центр первой окружности совпадает с началом координат, а радиус равен 106. Вторая окружность — любая, проходящая через точки (−106, 0) и (0, 0). В обоих примерах возможны и другие правильные ответы.

Система оценивания

Правильные решения для тестов, в которых 2 ≤ n ≤ 50, будут оцениваться из 50 баллов.

Формат входного файла

Первая строка входного файла содержит целое число n — количество размещенных Митей камушков на поле. Последующие n строк содержат целочисленные координаты камушков (xi, yi) — в каждой строке по одной паре координат, разделенных пробелом. Никакие два камушка не размещаются в одной точке. Гарантируется, что ответ для заданного набора камушков существует.

Формат выходного файла

Выходной файл должен содержать две строки. Первая строка должна содержать последовательность номеров всех камушков, которые принадлежат первой окружности, вторая строка — последовательность номеров всех камушков, которые принадлежат второй окружности. Считается, что камушки пронумерованы от 1 до n в порядке их следования во входных данных. Каждый камушек должен встречаться хотя бы в одной из двух последовательностей. Если камушек встречается в обеих последовательностях, то это обозначает, что он находится на пересечении окружностей. Нумерация окружностей не имеет значения, то есть выводить две последовательности можно в любом порядке. Числа в последовательностях можно также выводить в произвольном порядке. Каждая из последовательностей должна содержать не менее одного числа. Все числа в строках должны быть разделены пробелами. Если вариантов расположения окружностей несколько, можно выбрать любой из них.

Ограничения

2 ≤ n ≤ 2000; −106 ≤ xi, yi ≤ 106

Примеры тестов

№ Входной файл (circles.in) Выходной файл (circles.out)
1 
7
1 -1
0 0
1 1
3 1
3 -1
2 0
4 0

1 2 3 6 
4 5 6 7
2 
5
-1000000 0
0 1000000
1000000 0
0 -1000000
0 0

1 2 3 4 
5
0.037s 0.007s 15