Задача G. Мосты-горки ≡

Условие

Выбор подходящего проекта строительства моста на остров Русский — задача не из лёгких: ведь существует много разновидностей мостов.

В Академии был разработан новый тип мостов — мосты-горки. Эти мосты устанавливаются между двумя островами, один из которых должен быть высоким, а другой низким. Чтобы попасть с высокого острова на низкий, достаточно просто скатиться по мосту, как по горке. При этом даже не нужно тратить топливо! К тому же при достаточной массе автомобиля езда превращается в увлекательный аттракцион.

Но у мостов-горок есть и недостатки:

1. Мост должен быть идеально прямым: массивные автомобили могут не справиться с поворотами на большой скорости.
2. Конструкция мостов-горок такова, что один мост не может проходить над другим мостом, то есть мосты не должны пересекаться друг с другом.

Ввиду заинтересованности правительства в мостах-горках в Академии была организована лаборатория по их исследованию. В лабораторных условиях была создана модель архипелага, в котором N высоких и N низких островов представлены точками на плоскости, причём никакие три острова не лежат на одной прямой. Требуется построить ровно N мостов-горок между островами так, чтобы на каждом острове был мост. Как высокие, так и низкие острова пронумерованы от 1 до N.

Первый пример теста соответствует рисунку справа. Тёмными изображены острова с номером 1, а светлыми — с номером 2. Если соединить тёмные острова со светлыми, то мосты будут пересекаться.

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

Входной содержит число N, за которым следует N пар чисел X_i Y_i — координаты высоких островов, а затем N пар чисел x_i y_i — координаты низких островов.

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

Выходной файл должен содержать N пар чисел p_i q_i — номера островов, соединённых мостом, где p_i — номер высокого острова, q_i — номер низкого острова. Пары можно выводить в произвольном порядке. Если решений несколько, выведите любое из них.

Если N мостов-горок построить невозможно, то выходной файл должен содержать единственное число  − 1.

Ограничения

1 ≤ N ≤ 1000,  − 10⁵ ≤ X_i, Y_i, x_i, y_i ≤ 10⁵.

Все числа во входном файле целые.

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

2
0 0
1 0
-2 -3
2 -3

1 1
2 2

5
1 0
2 2
-1 0
0 -3
-2 -3
4 -2
2 -2
1 -1
-1 -1
-3 2

1 3
4 1
2 2
5 4
3 5

Разбор

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

Вначале определим, с каким островом нужно соединять самый левый остров.

Для этого отсортируем все острова, кроме самого левого, по возрастанию полярного угла относительно него и пронумеруем их от 1 до N − 1. Будем считать, что самый левый остров высокий (случай, когда он низкий, рассматривается аналогично).

• Если остров с номером 1 низкий, то соединим его с самым левым островом, а затем повторим наш алгоритм для множества всех остальных островов.
• Если остров с номером N − 1 низкий, то поступим точно так же, как в предыдущем случае (см. Рис. 1).

• Если острова с номерами 1 и N − 1 высокие, то существует низкий остров с номером i, такой, что среди всех островов с номерами, меньшими i, высоких и низких островов поровну (см. Рис. 2). Тогда соединим i-й остров с самым левым. Затем повторим наш алгоритм сначала для островов с номерами 1, 2, ..., i − 1, а потом для островов с номерами i + 1, i + 2, ..., N − 1.

  Докажем, что найдётся низкий остров с номером i, такой, что среди всех островов с номерами, меньшими i, высоких и низких островов поровну.

  Рассмотрим последовательность чисел a₁, a₂, ..., a_N − 1, в которой a_k = 1, если остров с номером k низкий, и a_k =  − 1, если остров с номером k высокий.

  Пусть S_k = a₁ + a₂ + ...  + a_k. Заметим, что S_N − 1 = 1. Так как a_N − 1 =  − 1, то S_N − 2 = 2. При этом S₁ =  − 1, причём S_k + 1 отличается от S_k ровно на 1.

  Поэтому найдётся такое i, что 1 < i < N − 2 и S_i = 1.

  Если a_i = 1, то i-й остров низкий и S_i − 1 = 0, значит, среди островов с номерами 1, 2, ... i − 1 высоких и низких островов поровну, что и требовалось доказать.

  Если же a_i =  − 1, то мы можем принять i за N − 1 (убрать лишние острова) и повторить рассуждения. В конце концов мы найдём искомое i.

На рисунке показан пример работы алгоритма.

Докажем, что алгоритм работает верно, когда количество островов равно N. Предположим по индукции, что алгоритм работает верно, т.е. строит не пересекающиеся мосты, когда количество островов меньше N.

Все мосты можно разделить на три класса.

1. Мост, соединяющий самый левый остров с i-м.
2. Мосты, построенные при первом дополнительном вызове алгоритма.
3. Мосты, построенные при втором дополнительном вызове алгоритма.

Докажем, что любые два моста не пересекаются. Если оба моста принадлежат второму классу или оба моста принадлежат третьему классу, то они не пересекаются в силу нашего предположения, что алгоритм работает верно, когда количество островов меньше N.

Если один мост принадлежит второму классу, а другой - третьему классу, то они не пересекаются, потому что лежат по разные стороны от прямой, содержащей мост из первого класса.

По той же причине мост из первого класса не пересекается ни с каким мостом.

Итак, мосты не пересекаются друг с другом, поэтому алгоритм работает верно.