printРабочее место участника

printЗадачи

1016. Мосты-горки

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Выбор подходящего проекта строительства моста на остров Русский – задача не из лёгких: ведь существует много разновидностей мостов.
В Академии был разработан новый тип мостов – мосты-горки. Эти мосты устанавливаются между двумя островами, один из которых должен быть высоким, а другой низким. Чтобы попасть с высокого острова на низкий, достаточно просто скатиться по мосту, как по горке. При этом даже не нужно тратить топливо! К тому же при достаточной массе автомобиля езда превращается в увлекательный аттракцион.
Но у мостов-горок есть и недостатки:
  • Мост должен быть идеально прямым: массивные автомобили могут не справиться с поворотами на большой скорости.
  • Конструкция мостов-горок такова, что один мост не может проходить над другим мостом, то есть мосты не должны пересекаться друг с другом.
Ввиду заинтересованности правительства в мостах-горках в Академии была организована лаборатория по их исследованию. В лабораторных условиях была создана модель архипелага, в котором `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^5\ ≤\ X_i,\ Y_i,\ x_i,\ y_i\ ≤\ 10^5`.
Все числа во входном файле целые.

Пример ввода 1

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

Пример вывода 1

1 1
2 2

Пример ввода 2

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

Пример вывода 2

1 3
4 1
2 2
5 4
3 5
Источник: Г. Гренкин, ДВГУ, Весенний турнир, 2007
loading