Двоє чоловіків Японських Альп
Двоє досвідчених альпіністів планують здійснити першу в історії спробу: вони починають з двох точок однакової висоти на гірському хребті, рухаються вперед-назад по одному маршруту, зберігаючи свої висоти рівними, і зрештою зустрічаються в одній точці на маршруті. Мудрець сказав їм, що якщо на маршруті немає точки нижче за стартові точки (однакової висоти), то існує принаймні один спосіб здійснити цю спробу. Це і є причиною, чому двоє альпіністів вирішили почати планувати цю незвичайну спробу.
Альпіністи вже мають альтиметри (прилади, що вказують висоту) та засоби зв'язку, необхідні для підтримки рівності висот. Вони також обрали маршрут для спроби: маршрут складається з послідовних відрізків без відгалужень; дві стартові точки знаходяться на двох кінцях маршруту; немає жодної точки нижче за дві стартові точки однакової висоти. Ілюстрація маршруту наведена на Рисунку 1 (цей рисунок відповідає першому набору даних з прикладу вхідних даних).
Рисунок 1: Ілюстрація маршруту
Спроба повинна бути можливою для маршруту, як сказав мудрець. Однак, альпіністи не змогли знайти пару послідовностей рухів для здійснення спроби, оскільки вони не можуть підтримувати рівність висот без складної комбінації рухів вперед і назад. Наприклад, для маршруту, зображеного вище: альпініст, що починає з p_1 (скажімо, A), рухається до 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.