Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Две окружности - 2

(Время: 2 сек. Память: 16 Мб Сложность: 72%)

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

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

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

Входные данные

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

Никакие два камушка не размещаются в одной точке. Гарантируется, что ответ для заданного набора камушков существует.

Выходные данные

Выходной файл OUTPUT.TXT должен содержать две строки. Первая строка должна содержать последовательность номеров всех камушков, которые принадлежат первой окружности, вторая строка — последовательность номеров всех камушков, которые принадлежат второй окружности. Считается, что камушки пронумерованы от 1 до n в порядке их следования во входных данных.

Каждый камушек должен встречаться хотя бы в одной из двух последовательностей. Если камушек встречается в обеих последовательностях, то это обозначает, что он находится на пересечении окружностей.

Нумерация окружностей не имеет значения, то есть выводить две последовательности можно в любом порядке. Числа в последовательностях можно также выводить в произвольном порядке. Каждая из последовательностей должна содержать не менее одного числа. Все числа в строках должны быть разделены пробелами.

Если вариантов расположения окружностей несколько, можно выбрать любой из них.

Примеры

INPUT.TXTOUTPUT.TXT
17
1 -1
0 0
1 1
3 1
3 -1
2 0
4 0
6 1 2 3
4 7 5 6
25
-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).

В обоих примерах возможны и другие правильные ответы.


Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru