İşıq sönür (Qızıl)
Fermer Con yeni sağım aparatını quraşdırdı, lakin bu cihaz o qədər çox enerji sərf edir ki, bəzən anbarın işıqları sönür. Bu o qədər tez-tez baş verir ki, Bessi qaranlıqda çıxışa daha asan çatmaq üçün anbarın planını əzbərləyib.
Anbar sadə (öz-özünə kəsişməyən düzbucaqlı) və tam ədədi koordinatlarla (x[1], y[1]) ... (x[n], y[n]) saat əqrəbi istiqamətində sadalanan zirvələrlə təsvir olunur. Onun kənarları üfüqi (x oxuna paralel) və şaquli (y oxuna paralel) ola bilər. İlk kənar həm şaquli, həm də üfüqi ola bilər. Çıxış nöqtəsi (x[1], y[1]) nöqtəsində yerləşir. Bessi anbarın içində, bəzi zirvələrdən birində (x[i], y[i]) i > 1 üçün başlayır. O, yalnız anbarın perimetri boyunca saat əqrəbi istiqamətində və ya əks istiqamətdə hərəkət edə bilər. Onun məqsədi çıxışa minimal məsafə qət etməkdir. Bu, işıqlar yanıq olanda nisbətən asandır, çünki o, cari mövqedən çıxışa daha qısa olan yolu seçməlidir - saat əqrəbi istiqamətində və ya əks istiqamətdə.
İşıqlar sönəndə, Bessi panikaya düşür və olduğu zirvəni unudur. Xoşbəxtlikdən, o hələ də anbarın dəqiq xəritəsini xatırlayır, buna görə də perimetr boyunca hərəkət edərək və hisslərini istifadə edərək mövqeyini hesablaya bilər. O, zirvədə duranda (başlanğıc zirvəsi də daxil olmaqla), həmin zirvədəki daxili bucağı hiss edə bilər və bu zirvənin çıxış olub-olmadığını deyə bilər. Anbar boyunca hərəkət edərkən, keçdiyi kənarın dəqiq uzunluğunu müəyyən edə bilər. Bessi aşağıdakı strategiyaya uyğun hərəkət edir: o, anbarın perimetri boyunca saat əqrəbi istiqamətində hərəkət edir, kifayət qədər bucaq və kənar hiss edənə qədər, hansı zirvədə olduğunu müəyyən etmək üçün. Bu nöqtədə o, çıxışa daha tez çatmaq üçün asanlıqla hesablaya bilər - saat əqrəbi istiqamətində hərəkət etməyə davam edərək və ya əks istiqamətə keçərək.
Bessiyə işıqlarda məsafə ilə müqayisədə qaranlıqda çıxışa yolunun nə qədər artacağını müəyyən etməyə kömək edin (bütün mümkün başlanğıc zirvələrini nəzərə alaraq).
Giriş Məlumatları
Birinci sətir n (4 ≤ n ≤ 200) ehtiva edir. Növbəti n sətirin hər biri anbarın saat əqrəbi istiqamətində keçilən nöqtələrini (x[i], y[i]) təsvir edən iki tam ədədi ehtiva edir. Bu tam ədədlər -10^5 ... 10^5 aralığındadır.
Çıxış Məlumatları
Ən pis başlanğıc mövqeyi üçün məsafənin nə qədər artacağını göstərən ən böyük ədədi çıxarın.
İzah
Bu nümunədə Bessi əvvəlcə 90 dərəcə bucaqda dayandığını hiss edə bilər, amma 2 3 4 zirvələrini ayırd edə bilmir. Saat əqrəbi istiqamətində kənar boyunca bir addım irəlilədikdən sonra Bessi ya çıxışa çatacaq, ya da bu kənarın uzunluğuna əsaslanaraq mövqeyini dəqiq müəyyən edə biləcək. O, aşağıdakı məsafələri əldə edəcək:
Əgər o, 2 zirvəsindədirsə: qaranlıqda 12 vahid məsafə qət edəcək (3 zirvəsinə qədər 1 vahid, sonra çıxışa qədər 11 vahid). İşıqlarda isə 10 vahid məsafə qət etməli olardı. Buna görə də bu zirvə üçün əlavə məsafə 2.
Əgər başlanğıc zirvəsi 3-dürsə: hər iki halda 11 vahid məsafə qət edəcək.
Əgər başlanğıc zirvəsi 4-dürsə: hər iki halda 1 vahid məsafə qət edəcək.
Ən pis hal 12 - 10 = 2. Buna görə də Bessi strategiyasını istifadə edərək, başlanğıc nöqtəsindən asılı olmayaraq qaranlıqda məsafənin işıqlarda məsafədən 2 vahiddən çox artmayacağına əmin ola bilər.