Зигзаг
Дано кілька точок на площині, і ваше завдання — розв'язати головоломку, з'єднавши їх зигзагоподібною лінією. Мета полягає в тому, щоб знайти зигзагоподібну лінію, яка проходить через усі задані точки з мінімальною кількістю поворотів. Якщо існує кілька таких ліній, потрібно вибрати найкоротшу з них.
Розгляньмо приклад з дев'ятьма точками, зображеними на Рисунку 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).
Ваше завдання — написати програму, яка розв'язує цю головоломку.
Вхідні дані
Вхід складається з кількох наборів даних, за якими слідує рядок, що містить один нуль. Кожен набір даних має наступний формат.
n
x_1 y_1
...
x_n y_n
Кожен елемент введення в наборі даних є невід'ємним цілим числом. Елементи в рядку розділені одним пробілом.
n — це кількість заданих точок. x_k та y_k (k = 1, ..., n) вказують на положення k-ї точки. Порядок точок не має значення. Ви можете припустити, що 2 ≤ n ≤ 10, 0 ≤ x_k ≤ 10, та 0 ≤ y_k ≤ 10.
Вихідні дані
Для кожного набору даних слід надрукувати мінімальну кількість точок повороту та довжину найкоротшої зигзагоподібної лінії з такою кількістю точок повороту, розділених пробілом в одному рядку. Довжина повинна бути у вигляді десяткового дробу з похибкою менше 0.0001 (= 1.0 × 10^{−4}).
Ви можете припустити, що мінімальна кількість точок повороту не перевищує чотирьох, тобто кількість відрізків не перевищує п'яти.
Прикладні розв'язки для перших чотирьох наборів даних у прикладі введення зображені на Рисунку 5 та 6.
Рисунок 5: Прикладні розв'язки для першого та другого наборів даних у прикладах введення.
Рисунок 6: Прикладні розв'язки для третього та четвертого наборів даних у прикладах введення.