Зигзаг
Дано несколько точек на плоскости. Ваша задача — соединить их зигзагообразной линией, которая проходит через все точки с минимальным числом поворотов. Если существует несколько таких линий, выберите самую короткую.
Рассмотрим пример с девятью точками, изображенными на Рисунке 1.
Рисунок 1: Девять данных точек
Зигзагообразная линия состоит из нескольких прямолинейных отрезков, и каждый отрезок должен проходить через две или более данных точек.
Линия может поворачивать в данных точках или в любом другом месте, и некоторые точки могут быть пройдены более одного раза.
Рисунок 2: Зигзагообразные линии с тремя точками поворота.
На Рисунке 2 (a) и (b) показаны две зигзагообразные линии с тремя точками поворота для того же набора точек, что и на Рисунке 1. Линия на Рисунке 2 (a) короче, чем на (b), и является решением, поскольку она самая короткая среди линий с минимальным числом поворотов.
На Рисунке 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.
Предполагается, что минимальное количество точек поворота не превышает четырех, то есть количество отрезков не превышает пяти.
Примерные решения для первых четырех наборов данных показаны на Рисунке 5 и Рисунке 6.
Рисунок 5: Примерные решения для первого и второго наборов данных.
Рисунок 6: Примерные решения для третьего и четвертого наборов данных.