Задача №111786. Пары точек
На плоскости своими координатами заданы \(N\) красных и \(N\) синих точек. Никакие три точки не принадлежат одной прямой. Необходимо построит \(N\) отрезков таких, что никакие два из них не пересекаются, каждый отрезок соединяет точки разного цвета, и каждая точка принадлежит ровно одному отрезку.
Напишите программу, которая по информации о размещении точек найдёт любое разбиение множества точек на \(N\) отрезков, каждый из которых соединяет синюю и красную точки. Причём, каждая точка принадлежит только одному отрезку и никакие два отрезка не пересекаются.
Первая строка содержит единственное натуральное число не больше 10 - количество входных тестовых блоков. Блоки идут один за другим. Каждый блок необходимо обработать отдельно. Первая строка каждого тестового блока содержит целое число \(N\) (1 ≤ \(N\) ≤ 2500) - количество точек одного цвета. Далее идут наборы координат синих точек, а потом – красных. Набор координат точек одного цвета задаётся \(N\) строками, каждая из которых содержит пару целых чисел - \(x\) и \(y\) координаты точки (|\(x\)| ≤ 10000, |\(y\)| ≤ 10000).
Вывести ответы для всех входных блоков без разделения. Каждая из \(N\) строк ответа каждого из блоков должна содержать пару целых чисел от 1 до \(N\) - номера синей и красной точек соединённых отрезком. Точки пронумерованы в том порядке, в котором они идут на входе отдельно по каждому цвету. В случае, если невозможно соединить точки отрезками без пересечений, единственная строка ответа для блока должна содержать число 0.
2 2 1 1 3 5 4 10 2 2 1 1 1 2 2
1 2 2 1 1 1