Объезд Бастер
Компания Green Parcel Services нанимает велосипедистов для доставки посылок по большому мегаполису. Сотрудники получают оплату в зависимости от расстояний, которые они преодолевают. Каждый велосипед оснащен системой GPS, фиксирующей его положение каждые несколько секунд. Последовательность позиций для одной доставки называется треком, и длина трека, определяемая как сумма евклидовых расстояний между последовательными точками, используется для расчета оплаты.
Недавний аудит показал, что некоторые треки самопересекаются, что указывает на ненужные отклонения. Ваша задача — написать программу, которая обработает данный трек и вычислит длину кратчайшего возможного трека от первой до последней точки. Этот трек должен быть частью исходного и может включать движение в обоих направлениях вдоль трека.
Входные данные
Ввод начинается с целого числа, которое указывает количество треков для сокращения. Описание каждого трека начинается с положительного целого числа N, представляющего количество точек в треке. Каждая из следующих N строк содержит два целых числа, разделенных пробелом, которые представляют x- и y-координаты точки в метрах. Точки перечислены в порядке их появления.
Две последовательные точки, образующие сегмент, будут находиться на расстоянии не более тридцати метров друг от друга, и сегмент не будет пересекаться более чем с двадцатью другими сегментами. Все x- и y-координаты находятся в диапазоне от -10000000 до 10000000, включительно. N варьируется от 1 до 100000, включительно.
Выходные данные
Для каждого входного трека выведите одно целое число, представляющее длину кратчайшего трека в метрах, округленную до ближайшего целого. Напоминание: Округление положительного числа R.xyz до ближайшего целого:
Если первая десятичная цифра (то есть x) меньше 5, округленное значение равно R.
В противном случае округленное значение равно R+1.