Задача A. Задача Штейнера (приближение)

Автор:Я. Штейнер   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

На плоскости задано N точек. Требуется соединить их сетью, состоящей из отрезков. Конечной точкой каждого отрезка может служить как любая из заданных точек, так и любая из M дополнительных точек, указанных вашей программой.

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

Формат входного файла

В начале входного файла содержится число N. За ним следует N пар вещественных чисел xi yi - координаты точек.

Формат выходного файла

В начале выходного файла должно содержаться число дополнительных точек M, за которым должны следовать M пар вещественных чисел ai bi — координаты точек.

Далее выведите N + M − 1 пару целых чисел от 1 до N + M — описание отрезков. То есть, дополнительным вершинам присваиваются номера от N + 1 до N + M в том порядке, в котором они выведены участником.

Ограничения

1 ≤ N ≤ 50

1 ≤ M ≤ 50

 − 104 ≤ xi, yi, ai, bi ≤ 104

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3
0 0
1 0
0 1
1
0.2 0.2
1 4
2 4
4 3

0.080s 0.018s 13