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

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

Условие

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

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

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

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

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

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

Далее выведите N+M1 пару целых чисел от 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.018s 0.005s 7