Архив Зеленоградского турнира

В одной далекой Африканской стране мы помогаем проводить электрификацию. Для этого недалеко от побережья каждого города запустили по водоплавающей АЭС и соединили их с ближайшими к ним домами. Цель данного проекта подсоединить к источнику энергии все дома каждого из городов. Каждый дом, подсоединенный к источнику электроэнергии, сам является источником электроэнергии. В некоторых участках местности можно также ставить дешевые деревянные электрические столбы. Однако в стране существует резкая нехватка электрического кабеля, поэтому протянутая электрическая сеть должна иметь минимальную длину. Стоимость столбов несоизмеримо меньше стоимости кабеля, поэтому количество электрических столбов может быть довольно большим.

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

t – число городов, затем следуют описания каждого из t городов. [t <= 50]
Описание каждого города начинается с числа N - количество домов в городе [3 <= N <= 3000]. Затем следуют ровно N строчек, на каждой из которых заданы два вещественных числа: x, y - координаты дома. [0.0 <= x, y <= 10000.0]

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

Для каждого теста необходимо вывести замкнутую электрическую сеть, т.е. все дома должны быть соединены между собой, либо напрямую, либо через другие дома, либо через электрические столбы. Для каждого теста на первой строчке выведите число M [0 <= M <= N] - количество деревянных электрических столбов. Далее на каждой из следующих M строчек выведите координаты каждого из столбов x, y [0.0 <= x, y <= 10000.0]. Далее выведите число K равное количеству требуемых участков кабеля. [N+M-1 <= K <= (M+N)*(M+N-1)/2]. И на каждой из следующих K строчек выведите два целых числа i, j - индексы соединяемых домов или столбов. Индексы у домов начинаются с 0 и заканчиваются на N-1, индексы столбов начинаются с N и заканчиваются на N+M-1.

Начисление очков

Количество очков, полученное за данную задачу total_score = (200+time)*(score_1+score_2+...score_t)/200. Где score_i - равно длине электрического кабеля потраченного на электрификацию i-го города, а time - время работы программы.

Пример

Входные данные:
1
4
1.0 1.0
1.0 11.0
11.0 1.0
11.0 11.0

Выходные данные:
1
6.0 6.0
4
0 4
1 4
2 4
4 3

Положим, что программа работала 10 секунд. Длина кабеля score_1 = 20*sqrt(2). В этом случае количество очков полученных за программу будет равно 29.698485