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