Detour Buster
The Green Parcel Services şirkəti, böyük bir metropol şəhərində bağlamaları çatdırmaq üçün velosipedçiləri işə götürür. İşçilər, çatdırdıqları bağlamalar üçün getdikləri məsafələrə əsasən ödəniş alırlar. Hər bir şirkət velosipedi, hər bir neçə saniyədə bir mövqeyini qeyd edən qlobal mövqe təyinetmə sistemi ilə təchiz olunub. Bir çatdırılma üçün mövqelərin ardıcıllığı iz adlanır və izin uzunluğu, ardıcıl qeyd olunan nöqtələr arasında olan evklid məsafələrinin cəmi, işçinin ödənişini hesablamaq üçün istifadə olunur.
Son yoxlamalar göstərdi ki, bəzi izlər öz-özünə kəsişir və bu, bəzi işçilərin lazımsız döngələr etdiyini göstərir. Sizin vəzifəniz, verilmiş izi işləyərək, orijinal izdən ilk nöqtədən son nöqtəyə qədər olan ən qısa mümkün izin uzunluğunu hesablamaq üçün bir proqram yazmaqdır. Ən qısa mümkün iz, orijinal izin bir hissəsi olmalıdır və orijinal iz boyunca eyni və ya əks istiqamətdə hərəkət etməyi əhatə edə bilər.
Giriş verilənləri
Giriş, qısaldılmalı olan izlərin sayını təmsil edən bir tam ədədlə, öz xəttində başlayır. Hər bir iz təsviri, izi təyin edən qeyd olunan nöqtələrin sayını təmsil edən müsbət tam ədəd N ilə, öz xəttində başlayır. Sonrakı N sətirin hər biri, iz üzərində bir nöqtənin x və y koordinatlarını metrlə təyin edən iki tam ədəd, tək boşluqla ayrılmış, ehtiva edir. Nöqtələr iz üzərində görünmə sırasına görə sıralanır.
Ardıcıl iki nöqtə, bir seqment təşkil edəcək, otuz metrdən çox olmayacaq və bir seqment iyirmidən çox digər seqmentlə kəsişməyəcək. Bütün x- və y-koordinatları -10000000 və 10000000 arasında, daxil olmaqla, dəyərlərə malikdir. N dəyərləri 1 və 100000 arasında, daxil olmaqla, dəyişir.
Çıxış verilənləri
Hər bir giriş izi üçün çıxış, öz xəttində olan tək bir tam ədəddən ibarətdir ki, bu da ən qısa izin uzunluğunu metrlə göstərir. Cavab ən yaxın tam ədədə yuvarlanmalıdır. Xatırlatma: Müsbət bir R.xyz ədədini ən yaxın tam ədədə yuvarlamaq:
Əgər ilk onluq yer (yəni x) 5-dən kiçikdirsə, onda yuvarlanmış dəyər R-dir.
Əks halda, yuvarlanmış dəyər R+1-dir.