Зигзаг#5795
Дано кілька точок на площині, і ваше завдання — розв'язати головоломку, з'єднавши їх зигзагоподібною лінією. Мета полягає в тому, щоб знайти зигзагоподібну лінію, яка проходить через усі задані точки з мінімальною кількістю поворотів. Якщо існує кілька таких ліній, потрібно вибрати найкоротшу з них.
Розгляньмо приклад з дев'ятьма точками, зображеними на Рисунку 1.
Рисунок 1: Задані дев'ять точок
Зигзагоподібна лінія складається з кількох прямих відрізків, причому кожен відрізок має проходити через дві або більше заданих точок.
Лінія може повертати в деяких із заданих точок або в будь-якому іншому місці. Деякі точки можуть бути пройдені більше одного разу.
Рисунок 2: Зигзагоподібні лінії з трьома точками повороту.
На Рисунку 2 (a) та (b) зображені дві зигзагоподібні лінії з трьома точками повороту для того ж набору точок, що й на Рисунку 1. Лінія на Рисунку 2 (a) коротша, ніж на (b), і є найкоротшою серед можливих, тому вона є розв'язком для дев'яти точок на Рисунку 1.
Інша зигзагоподібна лінія з чотирма точками повороту зображена на Рисунку 3. Її довжина менша, ніж у ліній на Рисунку 2, але кількість точок повороту більша, тому вона не є розв'язком.
довжина = 10.0
Рисунок 3: Зигзагоподібна лінія з чотирма точками повороту.
На Рисунку 4 (a) та (b) показані дві зигзагоподібні лінії для іншого набору точок.
Обидві мають однакову кількість точок повороту, але лінія на (a) довша, ніж на (b). Проте розв'язком є (a), оскільки один з відрізків на (b) проходить лише через одну задану точку, що порушує правило.
Рисунок 4: Зигзагоподібна лінія з двома точками повороту (a) та недійсна лінія (b).
Ваше завдання — написати програму, яка розв'язує цю головоломку.
Вхід складається з кількох наборів даних, за якими слідує рядок, що містить один . Кожен набір даних має наступний формат.
x_1\ y_1
x_n\ y_n
Кожен елемент введення в наборі даних є невід'ємним цілим числом. Елементи в рядку розділені одним пробілом.
— це кількість заданих точок. x_k та y_k (k = 1, \ldots, n) вказують на положення -ї точки. Порядок точок не має значення. Ви можете припустити, що 2 \leq n \leq 10, 0 \leq x_k \leq 10, та 0 \leq y_k \leq 10.
Для кожного набору даних слід надрукувати мінімальну кількість точок повороту та довжину найкоротшої зигзагоподібної лінії з такою кількістю точок повороту, розділених пробілом в одному рядку. Довжина повинна бути у вигляді десяткового дробу з похибкою менше (= 1.0 \times 10^{-4}).
Ви можете припустити, що мінімальна кількість точок повороту не перевищує чотирьох, тобто кількість відрізків не перевищує п'яти.
Прикладні розв'язки для перших чотирьох наборів даних у прикладі введення зображені на Рисунку 5 та 6.
Рисунок 5: Прикладні розв'язки для першого та другого наборів даних у прикладах введення.
Рисунок 6: Прикладні розв'язки для третього та четвертого наборів даних у прикладах введення.
Приклад 1