Жук2
Ətrafımızda çoxlu naviqasiya məsələləri mövcuddur. Bu məsələ Juk2 adlanan alqoritm haqqındadır.
Juk-alqoritmləri aşağıdakı naviqasiya məsələsini həll edir. İkiölçülü xəritə var ki, burada istənilən formalı maneələr, həmçinin başlanğıc və son nöqtə mövcuddur. S başlanğıc nöqtəsində dayanan "agent" var və onun vəzifəsi son nöqtə F-ə çatmaqdır. O, son nöqtənin koordinatlarını bilir və istənilən anda öz koordinatlarını müəyyən edə bilər. Agentin O(1) yaddaşı var, buna görə də maneələrin xəritəsini saxlaya bilmir. Xarici dünya haqqında məlumatı yalnız maneəyə toxunub-toxunmadığını müəyyən edərək əldə edə bilər. Agent maneələrin sərhədləri boyunca hərəkət edə bilər. Agentin vəzifəsi finişə çatmaq və ya bunun mümkün olmadığını bildirməkdir.
Juk2 alqoritmi, Juk-alqoritmləri cəminə aid olan, aşağıdakı kimi işləyir:
1. Aşağıdakı şərtlərdən biri baş verənə qədər F-ə doğru hərəkət edirik:
Son nöqtəyə çatılıb. Alqoritm dayanır.
Maneə ilə qarşılaşdıq. 2-ci addıma keçirik.
2. Cari nöqtəni H ilə işarələyək. Maneə ətrafında saat əqrəbi istiqamətində hərəkət edirik, aşağıdakı şərtlərdən biri baş verənə qədər:
Son nöqtəyə çatılıb. Alqoritm dayanır.
H nöqtəsinə çatılıb. O zaman son nöqtə əlçatmazdır. Alqoritm dayanır.
SF xətti üzərində yerləşən L nöqtəsinə çatılıb, |LF| < |HF| və bu halda F-ə doğru hərəkət etmək mümkündür, maneəyə dərhal toxunmadan. Bu halda 1-ci addıma keçirik.
Alqoritmin düzgünlüyünü sübut etmək olar. Yəni agentin son nöqtəyə sonlu vaxtda çatacağını (nəticə yolunun uzunluğu sonludur) və ya son nöqtənin sonlu vaxtda əlçatmaz olduğunu bildirəcəyini.
Verilmiş maneələr cəmi və başlanğıc və son nöqtənin koordinatlarına görə, agentin Juk2 alqoritminə uyğun olaraq keçəcəyi yolun uzunluğunu müəyyən etmək lazımdır.
Giriş verilənləri
Birinci sətir beş tam ədəd n, x_S, y_S, x_F, y_F - maneələrin sayı və başlanğıc və son nöqtənin koordinatlarını ehtiva edir.
Qalan giriş məlumatları maneələri təsvir edir. Hər bir maneənin təsviri onun içindəki zirvələrin sayı m (m ≥ 3) ilə başlayır. Növbəti m sətir maneələrin zirvələrinin tam ədədi koordinatlarını x_i, y_i saat əqrəbi istiqamətində təsvir edir. Maneələr öz-özünə kəsişmələr və ya toxunmalar etmir.
Bütün maneələrdəki zirvələrin ümumi sayı 300000-i keçmir. Heç bir koordinat modulu 10^6-dan böyük deyil.
Heç bir maneə zirvəsi SF xətti üzərində yerləşmir. Başlanğıc və son nöqtələr maneələrdən kənarda yerləşir. Heç bir iki maneə ortaq nöqtəyə malik deyil. SF xəttini kəsən hər hansı iki nöqtə A və B üçün ya |AF| = |BF|, ya da ||AF| - |BF|| > 10^{-6} şərti yerinə yetirilir.
Çıxış verilənləri
Agentin təsvir olunan alqoritmə uyğun keçdiyi yolun uzunluğunu çıxarın. Səhv 10^{-6} səviyyəsində qəbul edilə bilər.