Дипломатичні стосунки
З метою мінімізації витрат на міністерство Міністр закордонних справ розмірковував наступним чином. Не достатньо, щоб кожна країна підтримувала дипломатичні стосунки з не більш ніж однією іншою країною. Так як є більше ніж дві країни у світі, деякі країни не сможуть спілкуватись одна з одною через мережу дипломатів.
Тепер, давайте припустимо, що кожна країна підтримує дипломатичні стосунки з не більш ніж двома іншими країнами. По неписаним дипломатичним законам кожна країна розглядається як рівноправна у відношенні до інших країн. З цього випливає, що кожна країна підтримує дипломатичні стосунки точно з двома іншими країнами.
Міжднародні топологи запронували структуру, яка відповідає цим потребам. Нехай країни утворюють круг, і нехай кожна країна має дипломатичні стосунки зі своїм лівим і правим сусідом. У реальному світі міністерство закордонних справ знаходиться всередині кожної країни. Для простоти будемо вважати, що його місцезнаходження задано у якості відправної точки на двомірній площині. Якщо ви підключите зв'язки закордонних дипломатичних представництв відповідних країн по прямій, то результатом будет многокутник.
У даний час потрібно створити місця для двостороні дипломатичних зустрічей. Знову ж таки, по дипломатиним міркуванням необхідино, щоб обидва дипломати їздили до місця зустрічі на однакові відстані. Також з міркувань ефективності відстань такої подорожі повинна бути зведена до мінімуму. Будьте готові до розв'язання цієї задачі!
Вхідні дані
Вхідні дані містять декілька тестових випадків. Кожен тест починається з числа N – кільклсті країн-участиць. Можна вважати, що N ≥ 3 є числом непарним. Далі йде N пар х і у-координат, які позначають місця самих міністреств закордонних справ. Координати міністерств закордонних справ є цілими числами, абсолютна величина яких менше, ніж 10^12. Країни розміщено у тому ж порядку, як вони появляються у вхідних даних. Кріме того, перша країна є сусідом останньої країни у списку. Вхідні дані завершуються з кінцем файлу.
Вихідні дані
Для кожного випадку вхідних даних виведіть N - кількість місць проведення зустрічей, а потім х- і у-координати їх місцезнаходження. Порядок місць зустрічей повинен бути таким же, як цо вказано у вхідних даних. Почність з місця проведення зустрічей для перших двох країн і так далі до останніх двох країн. Останнім у вихідних даних повинен бути опис місця зустрічей для N-ї і першої країни. Координати виводьте з точністю 6 знаків після десяткової крапки.
Зауваження
Звергінть увагу, що вхідні і вихідні дані можуть бути тлумачені як полігони. Відношення між вхідним і вихідним зразками полігонів показано на рисунку до задачі 1047. Щоб створити додаткові прикладу такого зразка можете використовувати ваші приклади до розв'язання цієї задачі.