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