eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Дипломатические отношения

Дипломатические отношения

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

В целях минимизации расходов на министерство Министр иностранных дел рассуждал следующим образом. Не достаточно, чтобы каждая страна поддерживала дипломатические отношения с не более чем одной другой страной. Поскольку есть более чем две страны в мире, некоторые страны не смогут общаться друг с другом через сеть дипломатов.

Теперь, давайте предположим, что каждая страна поддерживает дипломатические отношения с не более чем двумя другими странами. По неписанным дипломатическим законам каждая страна рассматривается как равноправная по отношению к другим странам. Из этого следует, что каждая страна поддерживает дипломатические отношения с точно двумя другими странами.

Международные топологи предложили структуру, которая соответствует этим потребностям. Пусть страны образуют круг, и пусть каждая страна имеет дипломатические отношения со своим левым и правым соседом. В реальном мире, министерство иностранных дел находится внутри каждой страны. Для простоты будем считать, что его местоположение задано в качестве отправной точки в двумерной плоскости. Если вы подключите связи зарубежных дипломатических представительств соответствующих стран по прямой, то результатом будет многоугольник.

В настоящее время необходимо создать места для двусторонних дипломатических встреч. Опять же, по дипломатическим соображениям необходимо, чтобы оба дипломата ездили до места встречи на равные расстояния. Также по соображениям эффективности расстояние такого путешествия должно быть сведено к минимуму. Будьте готовы к решению этой задачи!

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

Входные данные содержат несколько тестовых случаев. Каждый тест начинается с числа N – количества стран-участниц. Можно считать, что N3 есть число нечетное. Далее следуют N пар х и у-координат, обозначающих места ведомств иностранных дел. Координаты министерств иностранных дел являются целыми числами, абсолютная величина которых меньше, чем 10^12. Страны расположены в том же порядке, как они появляются на входе. Кроме того, первая страна является соседом последней страны в списке. Входные данные прекращаются с окончанием файла.

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

Для каждого случая входных данных выведите N - количество мест проведения встреч, а затем ху-координаты их местоположения. Порядок мест встречи должен быть таким же, как это указано во входных данных. Начните с места проведения встреч для первых двух стран и так далее до последних двух странах. Последним в выходных данных должно быть описание места встречи для N-й и первой страны. Координаты выводите с точностью 6 знаков после десятичной точки.

Замечание

Обратите внимание, что входные и выходные данные могут быть истолкованы как полигоны. Отношения между входным и выходным образцами полигонов показано на рисунке к задаче 1047. Чтобы создать дополнительные примеры такого образца можете использовать ваши примеры к решению этой задачи.

Пример

Входные данные #1
5 10 2 18 2 22 6 14 18 10 18
3 -4 6 -2 4 -2 6
3 -8 12 4 8 6 12
Выходные данные #1
5 14.000000 2.000000 20.000000 4.000000 18.000000 12.000000 12.000000 18.000000 10.000000 10.000000
3 -3.000000 5.000000 -2.000000 5.000000 -3.000000 6.000000
3 -2.000000 10.000000 5.000000 10.000000 -1.000000 12.000000