Пары
Пары
На дипломатическом приёме находится N дипломатов, причём число N чётно. Каждый дипломат ведё беседу ровно с одним другим дипломатом. Разведке одной из стран удалось получить фотографии с приёма. Изучив эти фотографии, аналитики установили координаты каждого из дипломатов и попытались восстановить, кто из них с кем беседует. Алгоритм восстановления следующий: из дипломатов, ещё не распределённых по парам, выбираются двое, расстояние между которыми минимально, и принимается, что они беседуют между собой. В случае, если существует несколько пар дипломатов, у которых растояния минимальны, вибирается пара с лексикографически наименьшим номером (все дипломаты пронумерованы по номерам их досье в разведке от 1 до N, внутри пары собеседников дипломат с нименьшим номером указывается первым).
Вам поручено реализовать этот алгоритм.
Giriş verilənləri
Первая строка входного файла содержит чётное число N (2 ≤ N ≤ 300). В последующих N строках заданы координаты x_i и y_i каждого дипломата, причём в i-й строке заданы координаты дипломата с номером досье i. Для различных дипломатов как минимум одна из существующих координат различна. Координаты не превосходят по абсолютной величине 10^8.
Çıxış verilənləri
Выведите N/2 строк - номера пар дипломатов, беседующих между собой. Пары выводятся в лексикографическом порядке, внутри каждой пары первое число должно быть меньше второго.
Nümunə
6 0 2 3 2 0 0 1 0 0 -2 2 -2
1 2 3 4 5 6