Bug2#2259

Bug2

3 saniyə

256 meqabayt

Çətin

Ətrafımızda müxtəlif naviqasiya problemləri mövcuddur. Bu tapşırıq isə Bug2 adlanan alqoritm haqqındadır.

Bug alqoritmləri aşağıdakı naviqasiya problemini həll edir. İkitərəfli xəritədə ixtiyari formalı maneələr yerləşir, başlanğıc və son nöqtələr verilir. Bundan başqa, başlanğıc nöqtəsində $S$ dayanan və vəzifəsi son nöqtə $F$ -a çatmaq olan agent var. Agent son nöqtənin koordinatlarını bilir, və istənilən anda öz koordinatlarını müəyyən edə bilir. Agentin $O (1)$ yaddaşı var, yəni maneələrin xəritəsini yadda saxlaya bilmir. Xarici aləmlə yeganə əlaqə üsulu — toxunub-toxunmadığını anlamaqdır. Agent maneə ətrafında hərəkət edərək, onun sərhədini izləyə bilir. Məqsəd çatmaq mümkün olduqda son nöqtəyə çatmaq, əks halda isə bu barədə dəqiq məlumat verməkdir.

Bug2 alqoritmi, Bug alqoritmləri ailəsinə məxsus olaraq, aşağıdakı kimi işləyir:

1. Aşağıdakı hadisələrdən biri baş verənədək $F$ nöqtəsinə doğru hərəkət et:

Son nöqtəyə çatıldı. Onda alqoritm dayanır.
Maneəyə rast gəlinir. Onda keçid et 2-ci mərhələyə.

2. Cari nöqtəni $H$ kimi təyin et. Maneənin sərhədi ilə saat əqrəbi istiqamətində hərəkət et, aşağıdakı hadisələrdən biri baş verənədək:

Son nöqtəyə çatıldı. Onda alqoritm dayanır.
$H$ nöqtəsinə yenidən qayıdıldı. Onda son nöqtəyə çatmaq mümkün deyil və alqoritm dayanır.
$L$ nöqtəsinə çatıldı, bu nöqtə $SF$ düz xəttinin üzərində yerləşir, $∣ LF ∣ < ∣ HF ∣$ |\textbf{LF}| < |\textbf{HF}| və buradan maneəyə dərhal toxunmadan $F$ -ə doğru hərəkət etmək mümkündür. Bu halda, yenidən 1-ci mərhələyə qayıdılır.

Alqoritmin düzgünlüyünü sübut etmək olar: yəni, əgər mümkündürsə, son nöqtəyə sonlu zamanda (yəni, yaranan yolun uzunluğu sonludur) çatdığını və əks halda əlçatmazlıq faktını sonlu zamanda düzgün qeyd etdiyini.

Qırıq xətli maneələr və başlanğıc və son nöqtələr verildiyi halda, Bug2 alqoritminin idarə etdiyi agentin keçəcəyi yolun uzunluğunu müəyyən edin.

Giriş

Giriş faylının birinci sətirində beş tam ədəd $n$ , $x_{S}$ x_S, $y_{S}$ y_S, $x_{F}$ x_F, $y_{F}$ y_F yazılmışdır — maneələrin sayı və başlanğıc və son nöqtənin koordinatları.

Daha sonra maneələr təsvir olunur. Hər bir təsvir, birinci sətirində bir tam ədəd $m$ ( $m \geq 3$ m \ge 3) — maneənin təpə nöqtələrinin sayı verilir. Sonrakı $m$ sətirdə isə maneənin təpə nöqtələrinin koordinatlarını göstərən iki tam ədəd $x_{i}$ x_i, $y_{i}$ y_i verilir. Təpə nöqtələri saat əqrəbi istiqamətində verilir. Maneənin öz-özünə kəsişmələri və ya toxunan nöqtələri yoxdur.

Bütün maneələrin təpələrinin ümumi sayı $300000$ -dən çox deyil. Heç bir koordinat modulu $1 0^{6}$ 10^6-dan böyük deyil.

Heç bir maneə təpəsi $SF$ düz xəttinin üzərində yerləşmir. Həm başlanğıc, həm də son nöqtə hər hansı maneənin daxilində yerləşmir. Heç iki maneənin birgə nöqtəsi yoxdur. Əgər maneə sərhədi $SF$ xətti ilə $A$ və $B$ nöqtələrində kəsişirsə, ya $∣ AF ∣ = ∣ BF ∣$ |\textbf{AF}| = |\textbf{BF}|, ya da $∣∣ AF ∣ - ∣ BF ∣∣ > 1 0^{- 6}$ ||\textbf{AF}|-|\textbf{BF}|| > 10^{-6} olacaqdır.

Çıxış

Təsvir edilmiş alqoritmlə agentin keçəcəyi yolun uzunluğunu çıxışa yazın. $1 0^{- 6}$ 10^{-6} dəqiqliklə mütləq və ya nisbi xəta qəbul olunur.

Nümunələr

Nümunə 1