Tunb Hava Yolları
Tunb hava yolları, Fars körfəzində yerləşən bir neçə gözəl adaya uçuş planları təklif edir. Hər bir uçuş marşrutu, şəkildə göstərildiyi kimi, 2D xəritədə bir adadan başlayıb başqa adada bitən çoxbucaqlı bir yol şəklində təsvir edilir. Son zamanlarda hava yolları, uçuşlarının təhlükəsizlik səviyyəsini qiymətləndirməyə qərar verib. Uçuş planı üçün təhlükəsizlik tədbirlərindən biri, uçuş yolundakı bütün nöqtələr üçün təhlükəlilik (p) maksimumunu tapmaqdır. Burada təhlükəlilik (p), Fars körfəzindəki adalara p nöqtəsinin minimum Evklid məsafəsi kimi müəyyən edilir. Bu ölçü aşağı olduqda, hadisə baş verərsə sağ qalma ehtimalı yüksəkdir. Sizin vəzifəniz, verilmiş uçuş planı üçün bu təhlükəsizlik ölçüsünü hesablamaqdır.
Giriş verilənləri
Girişdə bir neçə test halı var. Hər bir test halı iki qeyri-mənfi tam ədəd n və m (0 ≤ n, m ≤ 20) olan bir sətirlə başlayır. Burada n Fars körfəzindəki adaların sayı, m isə uçuş yolunun təpə nöqtələrinin sayını göstərir. Daha sonra, hər biri yolun təpə nöqtələrinin koordinatlarını ilk nöqtədən son nöqtəyə qədər ehtiva edən m sətir gəlir. Nəhayət, hər bir test halı ayrı-ayrı çoxbucaqlar şəklində olan adaların təsviri ilə tamamlanır. Hər bir çoxbucaq üçün əvvəlcə bir sətirdə təpə nöqtələrinin sayı, t, verilir (t ən azı 3 və ən çox 30-dur). Növbəti t sətirdə çoxbucağın təpə nöqtələrinin koordinatları ya saat əqrəbi istiqamətində, ya da əksinə verilir; hər sətirdə iki tam ədəd var. Bütün koordinatlar -10000 və 10000 aralığında yerləşir. Giriş "0 0" (sitatları daxil etməyin) sətiri ilə bitir və bu test halı kimi işlənməməlidir.
Çıxış verilənləri
Hər bir test halı üçün yuxarıda müəyyən edilmiş təhlükəsizlik ölçüsünü tam olaraq üç ondalık rəqəmə yuvarlaqlaşdıraraq çıxarın.