Автор: | Я. Штейнер | Ограничение времени: | 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 |
|
|