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