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

Личное первенство УрГУ 2002

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

D. Дороги Акбардина

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Великий Акбардин, желая сделать перемещение в своем халифате как можно более быстрым, утвердил программу строительства новых дорог. Новые дороги должны быть устроены так, чтобы из каждого города можно было попасть в каждый и затратить при этом как можно меньше времени. Но Великий Акбардин и все его придворные математики совершенно не представляют, как такую задачу решить. Поэтому на первом этапе они решили построить абсолютно прямые и абсолютно ровные дороги между городами так, чтобы каждый город был соединен дорогой в точности с одним другим городом. При этом решили, что поскольку развилки существенно затрудняют движение, дороги не должны пересекаться.
Ваша задача — составить план первого этапа строительства дорог, зная расположение городов.

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

В первой строке находится чётное число N (N ≤ 10000). Далее следует N строк, каждая из которых содержит координаты очередного города — пару целых чисел xi, yi (−109 < xi, yi < 109). Никакие три города не лежат на одной прямой.

Результат

Выведите N/2 строк с описанием дорог, которые надо построить. Каждая дорога определяется парой чисел — номерами городов, соединяемых дорогой.

Пример

исходные данныерезультат
4
0 2
1 1
3 4
4 4
1 3
2 4
Автор задачи: Павел Атнашев
Источник задачи: Third USU personal programming contest, Ekaterinburg, Russia, February 16, 2002
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1178. Дороги Акбардина