eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Пары точек

Пары точек

Лимит времени 1.5 секунда
Лимит использования памяти 256 MiB

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

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

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

Первая строка содержит количество тестов, которые идут один за другим. Первая строка каждого тестоа содержит количество точек n (1 n 2500) одного цвета. Далее идут наборы координат синих точек, а потом – красных. Набор координат точек одного цвета задаётся n строками, каждая из которых содержит пару целых чисел x и y (|x|10000, |y| 10000)- координаты точки.

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

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

Пример

Входные данные #1
2
6
-1 4
0 0
1 7
4 6
9 4
8 0
3 5
5 1
6 5
8 3
2 6
0 3
5
-1 4
0 0
3 5
8 0
9 4
1 7
4 6
5 1
6 5
8 3
Выходные данные #1
2 1
1 6
3 5
4 2
6 3
5 4
1 1
5 2
4 5
3 4
2 3
Автор Тарас Галковский, Богдан Рублев
Источник 2010 XXIII Всеукраинская олимпиада по информатике, Киев, Март 22 - 26, тур 2