Дипломатичні стосунки#1046
З метою мінімізації витрат на закордонні справи було вирішено, що недостатньо, щоб кожна країна підтримувала дипломатичні відносини лише з однією іншою країною, оскільки, якщо у світі більше двох країн, деякі країни не зможуть спілкуватися через ланцюг дипломатів.
Припустимо тепер, що кожна країна підтримує дипломатичні відносини щонайбільше з двома іншими країнами. Відповідно до неписаних дипломатичних правил, кожна країна повинна бути поставлена у рівне становище, отже, кожна країна повинна підтримувати дипломатичні відносини рівно з двома іншими країнами.
Міжнародні топологи запропонували структуру для задоволення цих потреб: розташувати країни по колу, щоб кожна країна мала дипломатичні відносини з лівим і правим сусідами. На практиці дипломатичне представництво кожної країни знаходиться на її території, і для простої ідентифікації його місцезнаходження задано у вигляді точки на двовимірній площині. Якщо з'єднати дипломатичні офіси пов'язаних країн прямими лініями, отримаємо багатокутник.
Тепер потрібно визначити місця для двосторонніх дипломатичних зустрічей. З дипломатичних міркувань обидва дипломати мають подолати однакову відстань до місця зустрічі. Для ефективності ця подорож має бути мінімальною. Готуйтесь розв'язувати цю задачу!
Вхід містить кілька тестових випадків. Кожен тестовий випадок починається з цілого числа (N \ge 3) — кількості країн, яка завжди непарна. Далі йде пар цілих координат і (|x|, |y| < 10^{12}), які задають розташування дипломатичних офісів. Країни йдуть у даному порядку, а перша країна також є сусідом останньої. Ввід закінчується при досягненні кінця файлу.
Для кожного тестового випадку виведіть — кількість місць проведення зустрічей, а потім координати та кожного місця. Порядок місць проведення зустрічей має відповідати порядку у вхідних даних: спочатку місце зустрічі для перших двох країн, далі за цим порядком, закінчуючи місцем для -ї та першої країни. Координати слід наводити із знаками після десяткової крапки.
Приклад 1
Зверніть увагу, що вхід і вихід можна сприймати як багатокутники. Взаємозв'язок між багатокутником на вході і виході проілюстрований на рисунку для Задачі 1047. Додаткові приклади вхідних даних можна отримати за допомогою ваших розв'язків до цієї задачі.