| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 6 | 2 | 1 | 20.000% |
Юный футболист Митя обнаружил на школьном футбольном поле две различные окружности, нарисованные едва заметной белой краской. Вспомнив истории о загадочных кругах на полях, он отметил эти окружности с помощью небольших камушков. Митя разложил на поле n камушков так, чтобы каждый из них находился на одной из окружностей или даже на их пересечении, если эти окружности пересекаются. Получилось так, что на каждой окружности размещался хотя бы один камушек. Обладая великолепным глазомером, Митя расположил камушки на окружностях абсолютно точно, без какой-либо погрешности.
На следующий день пошел дождь, краска стерлась, и нарисованные окружности исчезли, но все камушки остались на своих местах. Теперь Мите очень нужно найти доказательство необычного явления, свидетелем которого он был, то есть, восстановить окружности.
Требуется написать программу, которая по координатам камушков на поле находит вариант размещения их на двух несовпадающих окружностях.
Первая строка входного файла содержит целое число n — количество размещенных Митей камушков на поле (2 ≤ n ≤ 2000). Последующие n строк содержат целочисленные координаты (xi, yi) камушков — по одной паре координат, разделенных пробелом, в каждой строке (−106 ≤ xi, yi ≤ 106). Никакие два камушка не размещаются в одной точке.
Гарантируется, что ответ для заданного набора камушков существует.
Выходной файл должен содержать две строки. Первая строка должна содержать последовательность номеров всех камушков, которые принадлежат первой окружности, вторая строка — последовательность номеров всех камушков, которые принадлежат второй окружности.
Каждый камушек должен встречаться хотя бы в одной из двух последовательностей. Если камушек встречается в обеих последовательностях, то это обозначает, что он находится на пересечении окружностей. Считается, что камушки пронумерованы от 1 до n в порядке их следования во входных данных.
Нумерация окружностей не имеет значения, то есть выводить две последовательности можно в любом порядке. Числа в последовательностях можно также выводить в произвольном порядке. Каждая из последовательностей должна содержать не менее одного числа. Все числа в строках должны быть разделены пробелами.
Если вариантов расположения окружностей несколько, можно выбрать любой из них.
7 1 -1 0 0 1 1 3 1 3 -1 2 0 4 0
6 1 2 3 4 7 5 6
5 -1000000 0 0 1000000 1000000 0 0 -1000000 0 0
1 2 3 4 1 5
В первом примере одна из искомых окружностей имеет центр в точке с координатами (1, 0), а вторая — в точке с координатами (3, 0). Обе окружности имеют радиус равный 1.
Во втором примере центр первой окружности совпадает с началом координат, а радиус равен 106. Вторая окружность — любая, проходящая через точки (−106, 0) и (0, 0).
В обоих примерах возможны и другие правильные ответы.