eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач

Тур

Джон Доу, опытный пилот, любит путешествовать. Находясь в отпуске, он арендует небольшой самолет и начинает посещение красивых мест. Чтобы сэкономить деньги, Джон должен определить кратчайший замкнутый тур, который соединяет его точки назначения. Каждое направление представлено точкой в плоскости \textbf{pi = < xi, yi >}. Джон использует следующую стратегию: он начинает из крайней левой точки, потом идет строго слева направо до крайней правой точки, а затем он возвращается обратно к исходной точке. Известно, что все точки имеют различные \textbf{x}-координаты. Напишите программу, которая, учитывая заданное множество \textbf{n }точек на плоскости, вычисляет кратчайший замкнутый тур, который соединяет все точки согласно стратегии Джона. \InputFile Программа читает входные данные из текстового файла. Каждый набор данных в файле означает определенный набор точек. Для каждого набора данных сначала задано количество точек, а затем координаты точек, заданные в порядке возрастания \textbf{х-}координат. Пробелы могут быть в произвольном количестве во входных данных. Гарантируется, что входные данные являются корректными. \OutputFile Для каждого набора данных, ваша программа должна выводить результат в отдельной строке. Результатом является длина тура в виде десятичного числа с двумя цифрами после десятичной точки. Пример ввода/вывода находится в таблице ниже. Здесь есть два набора данных. Первый содержит \textbf{3 }точки, которые определяются их \textbf{x- }и \textbf{y- }координатами. Вторая точка, например, имеет \textbf{x-}координату \textbf{2}, и \textbf{y-}координату \textbf{3}. В результате для всего набора данных длина тура составляет \textbf{6.47} -- для первого набора данных, заданном в примере.
Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные #1
3
1 1
2 3
3 1
4
1 1
2 3
3 1
4 2
Выходные данные #1
6.47
7.89