Два человека из Японских Альп
Два опытных альпиниста задумали совершить уникальную попытку: они начинают в двух разных точках на одинаковой высоте на горном хребте, движутся по маршруту туда и обратно, поддерживая равенство своих высот, и в итоге встречаются в одной точке маршрута. Мудрец сказал им, что если на маршруте нет точки ниже начальных точек (одинаковой высоты), то попытка возможна. Воодушевленные этим, альпинисты решили приступить к планированию.
Они уже приобрели альтиметры и устройства связи, чтобы поддерживать равенство высот. Для попытки они выбрали маршрут, состоящий из последовательных отрезков без ответвлений, с двумя начальными точками на концах маршрута, и без точек ниже начальных. Иллюстрация маршрута представлена на Рисунке 1 (соответствует первому набору данных из примера ввода).
Рисунок 1: Иллюстрация маршрута
Попытка должна быть возможной, как сказал мудрец. Однако альпинисты не смогли найти последовательности движений, чтобы осуществить её, так как не могут поддерживать равенство высот без сложных комбинаций прямых и обратных движений. Например, для маршрута выше: альпинист A, начиная в p_1, перемещается в s, а альпинист B — из p_6 в p_5; затем A возвращается в t, а B перемещается в p_4; наконец, A прибывает в p_3, и одновременно B также прибывает в p_3. Это может быть гораздо сложнее, поэтому они попросили вас написать программу, чтобы найти для них пару последовательностей движений.
Может существовать несколько возможных пар последовательностей движений, и вам нужно найти ту, у которой наименьшая сумма длин. Длина измеряется вдоль поверхности маршрута, например, путь от (0, 0) до (3, 4) имеет длину 5.
Входные данные
Ввод состоит из нескольких наборов данных.
Первая строка каждого набора данных содержит целое число N (2 ≤ N ≤ 100), обозначающее количество точек на маршруте. Каждая из следующих N строк содержит координаты (x_i, y_i) (i = 1, 2, ..., N) точек: начальные точки — (x_1, y_1) и (x_N, y_N); отрезки маршрута соединяют (x_i, y_i) и (x_{i+1}, y_{i+1}) для i = 1, 2, ..., N−1. Здесь xi — горизонтальное расстояние от начальной точки x_1, а y_i — высота относительно начальной точки y_1. Все координаты — неотрицательные целые числа меньше 1000, и выполняется x_i < x_{i+1} для i = 1, 2, ..., N−1, и 0 = y_1 = y_N ≤ y_i для i = 2, 3, ..., N−1.
Конец ввода обозначается строкой с нулем.
Выходные данные
Для каждого набора данных выведите минимальную сумму длин (вдоль маршрута) последовательностей движений до встречи альпинистов в одной точке. Каждое значение должно иметь точность не более 0.01.