Джон Доу, досвічений пілот, любить подорожувати. Знаходячись у відпустці, він арендує невеликий літак і починає відвідувати красиві місця. Щоб зекономити гроші, Джон повинен визначити найкоротший замкнутий тур, який з'єднує його точки призначення. Кожен напрям пожано точкою на площині pi = < xi, yi >. Джон використовує наступну стратегію: він розпочинає з крайньої лівої точки, потім йде строго зліва праворуч до крайньої правої точки, а потім він повертається назад у почткову точку. Відомо, що усі точки мають різні x-координати.
Напишіть програму, яка, враховуючи задану множину n точок на площині, обчисляє найкоротший замкнутий тур, який з'єднує усі точки згідно стратегії Джона.
Програма читає вхідні дані з текстового файлу. Кожен набір даних у файлі позначає певний набір точок. Для кожного набору даних спочатку задано кількість точок, а потім координати точок, задані у порядку зростання х-координат. Пропуски можуть бути у довільній кількості у вхідних даних. Гарантується, що вхідні дані є коректними.
Для кожного набору даних ваша програма повинна виводити результат у окремому рядку. Результатом є довжина туру у вигляді десяткового числа з двома цифрами після десяткової крапки. Приклад введення/виведення знаходиться у таблиці нижче. Тут є два набори даних. Перший містить 3 точки, які визначаються їх x- та y- координатами. Друга точка, наприклад, має x-координату 2, і y-координату 3. У результаті для всього набору даних довжина туру складає 6.47 – для першого набору даних, заданому у прикладі.