Detour Buster#3051
Green Parcel Services şirkəti velosipedçiləri böyük bir metropol şəhərində bağlamaları çatdırmaq üçün işə cəlb edir və işçilər çatdırmada getməli olduqları məsafəyə görə ödəniş alırlar. Hər bir şirkət velosipedinə, mövqeyini hər bir neçə saniyədə bir qeyd edən qlobal mövqe sistemi quraşdırılmışdır. Bir çatdırmanın mövqelər ardıcıllığı trek adlanır və trek uzunluğu—ardıcıl qeydə alınmış nöqtələr cütləri arasındakı Evklid məsafələrinin cəmi—işçinin ödənişini hesablamaq üçün istifadə olunur.
Qeydə alınmış treklərin son yoxlamasında bəzi treklərin öz-özünə kəsişdiyi müəyyən olmuşdur ki, bu da bəzi işçilərin lazım olmayan döngələr etdiyini göstərir. Sizin vəzifəniz verilmiş trek üzrə mümkün olan ən qısa trek uzunluğunu hesablamaq üçün proqram yazmaqdır. Ən qısa mümkün trek başlanğıc nöqtəsindən son nöqtəyə qədər olan trekdə bir hissə olmalı və orijinal trek boyunca eyni və ya əks istiqamətdə hərəkət etmək daxil ola bilər.
Giriş bir sətrin özündə qısa olmalı olan treklərin sayını göstərən bir tam ədəd ilə başlayır. Hər bir trekin təsviri ayrıca sətrin özündə trekdəki qeydə alınmış nöqtələrin sayını göstərən müsbət tam ədəd ilə başlayır. Sonrakı sətrin hər biri, nöqtənin və koordinatlarını (metrlə) bir boşluqla ayrılmış şəkildə müəyyənləşdirən iki tam ədəd ehtiva edir. Nöqtələr trekdə ardıcıllıqla verilmişdir.
Hər iki ardıcıl nöqtə, bir seqment təşkil edərək, otuz metrdən artıq aralı olmayacaq və heç bir seqment iyirmidən çox digər seqmentlə kəsişməyəcək. Bütün və koordinatları və arasında, daxil olmaqla, yerləşir. ilə arasında, daxil olmaqla, ola bilər.
Hər bir giriş trek üçün çıxışda ayrıca bir sətrin özündə ən qısa trek uzunluğunu tam ədəd kimi, metrlə və ən yaxın tam ədədə yuvarlaqlaşdırılmış şəkildə çap edin.
Xatırlatma: Müsbət ədəd R.xyz-ni ən yaxın tam ədədə yuvarlaqlaşdırmaq üçün:
Əgər ilk onluq rəqəmi () -dən kiçikdirsə, cavab -yə bərabərdir.
Əks halda cavab R+1-dir.
Nümunə 1