e-olymp
Задачі

Пари точок

Пари точок

На площині своїми координатами задані N червоних та N синіх точок. Жодні три точки не належать одній прямій. Необхідно побудувати N відрізків таких, що ніякі два з них не перетинаються, кожен відрізок з’єднує точки різного кольору, і кожна точка належить рівно одному відрізку.

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

Вхідні дані

Перший рядок містить єдине натуральне число - кількість вхідних тестових блоків. Блоки слідують один за одним. Кожен блок необхідно обробити окремо. Перший рядок кожного тестового блоку містить ціле число N (1 N 2500) - кількість точок одного кольору. Далі слідують набори координат синіх точок, а потім – червоних. Набір координат точок одного кольору задається Nрядками, кожен з яких містить пару цілих чисел - x і y координати точки (|x| 10000, |y| 10000).

Вихідні дані

Вивести відповіді для всіх вхідних блоків без розділення. Кожен з N рядків відповіді кожного з блоків має містити пару цілих чисел від 1 до N - номери синьої та червоної точок сполучених відрізком. Точки пронумеровані в тому порядку, в якому вони слідують на вході окремо по кожному кольору. У випадку, якщо неможна сполучити точки відрізками без перетинів, єдиний рядок відповіді для блоку має містити число 0.

Ліміт часу 1.5 секунда
Ліміт використання пам'яті 256 MiB
Вхідні дані #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