İşıqlar Sönür (Qızıl)#10600
Fermer Con inəkxanasında yeni, müasir sağım maşını qurub, lakin bu maşın o qədər çox elektrik enerjisi sərf edir ki, bəzən elektrik kəsilməsinə səbəb olur! Bu, o qədər tez-tez baş verir ki, Bessi inəkxananın xəritəsini əzbərləyib, bu da qaranlıqda çıxışı tapmasını asanlaşdırır. Ancaq o, elektrik kəsilməsinin inəkxanadan tez çıxmaq qabiliyyətinə necə təsir etdiyini bilmək istəyir. Məsələn, o, çıxışı tapmaq üçün qaranlıqda nə qədər çox məsafə qət etməli ola biləcəyini anlamaq istəyir.
İnəkxana sadə (özünü kəsməyən) çoxbucaqlı ilə təsvir olunur, onun tam ədədli təpə nöqtələri saat əqrəbi istiqamətində sadalanaraq (x_1, y_1), \ldots, (x_n, y_n) kimi verilir. Onun tərəfləri növbələşir: üfüqi (x oxuna paralel) və şaquli (y oxuna paralel), bu zaman birinci tərəf hər iki tipdən biri ola bilər. Çıxış (x_1, y_1) nöqtəsində yerləşir. Bessi i \gt 1 olmaqla (x_i, y_i) təpələrindən birində, inəkxananın içərisində hərəkətə başlayır. O, yalnız sərhəd boyunca — saat əqrəbi istiqamətində və ya əks istiqamətdə — hərəkət edə bilər. Onun məqsədi çıxışa çatmaq üçün mümkün olan ən qısa məsafəni qət etməkdir. İşıq yanarkən bunu etmək, əlbəttə ki, olduqca sadədir: o, cari mövqeyindən çıxışa doğru ya saat əqrəbi istiqamətində, ya da əks istiqamətdə, daha qısa yolu seçərək hərəkət edə bilər.
Bir gün işıqlar sönür və Bessi çaşqınlıq içində hansı təpədə olduğunu unudur. Xoşbəxtlikdən, o hələ də inəkxananın dəqiq xəritəsini xatırlayır, ona görə də sərhəd boyunca hərəkət edərək və toxunma hissini istifadə edərək öz yerini müəyyən etməyə çalışa bilər. O, hər dəfə bir təpədə olduqda (o cümlədən başlanğıc təpəsində), həmin təpənin dəqiq daxili bucağını müəyyən edə bilər, həmçinin bu təpənin çıxış olub-olmadığını öyrənə bilər. İnəkxananın bir tərəfi boyunca hərəkət etdikdə isə, həmin tərəfi tam qət etdikdən sonra onun dəqiq uzunluğunu müəyyən edə bilər.
Bessi aşağıdakı strategiyanı seçir: o, hansı təpədə olduğunu birmənalı şəkildə müəyyən etmək üçün kifayət qədər bucaq və tərəf hiss edənə qədər inəkxananın sərhədi boyunca saat əqrəbi istiqamətində hərəkət edəcək. Bundan sonra o, çıxışa gedən ən qısa yolu asanlıqla müəyyən edə biləcək: ya saat əqrəbi istiqamətində hərəkətini davam etdirəcək, ya da istiqaməti dəyişib əks istiqamətdə hərəkət edəcək.
Bessiyə kömək edin ki, işıqlar yanarkən hərəkət etməklə müqayisədə, qaranlıqda hərəkət edərkən qət etdiyi məsafənin ən pis halda (bütün mümkün başlanğıc təpələr üzrə) nə qədər artacağının maksimum qiymətini müəyyən etsin.
Birinci sətirdə n~(4 \le n \le 200) tam ədədi verilir. Növbəti sətirdən hər birində inəkxana ətrafında saat əqrəbi istiqamətində gəzinti sırası ilə (x_i, y_i) nöqtələrini təsvir edən iki tam ədəd verilir. Bu tam ədədlər -10^5 \le x_i, y_i \le 10^5 diapazonundadır.
Verilən şərtdə təsvir olunan strategiyadan istifadə edərkən, bütün mümkün başlanğıc təpələri üzrə ən pis halda Bessinin qət etdiyi məsafənin nə qədər artacağının maksimum qiymətini çıxarın.
Bu misalda Bessi başlanğıcda bucağı dərəcə olan bir təpədə olduğunu müəyyən edə bilir, lakin , və ya nömrəli təpələrdən hansında olduğunu anlaya bilmir. O, saat əqrəbi istiqamətində bir tərəfi qət etdikdən sonra ya çıxışa çatır, ya da bu tərəfin uzunluğuna əsasən öz yerini birmənalı şəkildə müəyyən edə bilir. Onun qət etdiyi məsafələrə baxaq:
Əgər Bessi nömrəli təpədən başlayırsa, qaranlıqda vahid məsafə qət edir: nömrəli təpəyə çatmaq üçün vahid, sonra isə çıxışa qədər daha vahid. İşıq yanarkən isə ona cəmi vahid qət etmək kifayətdir. Beləliklə, bu başlanğıc təpəsi üçün əlavə məsafə vahiddir.
Əgər Bessi nömrəli təpədən başlayırsa, hər iki halda o, vahid qət edir.
Əgər Bessi nömrəli təpədən başlayırsa, hər iki halda o, vahid qət edir.
Deməli, bütün mümkün başlanğıc təpələri üzrə ən pis haldakı fərq 12 - 10 = 2-dir. Başqa sözlə, Bessi təminat verə bilər ki, haradan başlamasından asılı olmayaraq, öz strategiyasından istifadə edərkən qaranlıqda işıq yanarkəndən vahiddən çox olmayaraq daha çox məsafə qət edəcək.
Nümunə 1