Ən Qısa Uçuş Yolu
Kommersiya uçuşları statistik olaraq kifayət qədər təhlükəsizdir (sərnişin-kilometr başına ölüm sayına görə, yalnız Aya getmək daha təhlükəsizdir). Lakin hələ də ehtiyat tədbirləri və təhlükəsizlik qaydaları üçün səbəblər var. Erkən belə bir qayda, iki mühərrikli təyyarənin bütün uçuş marşrutu boyunca ən yaxın uyğun hava limanından həmişə 60 dəqiqə məsafədə olmasını tələb edən "60-dəqiqə qaydası" idi. Müxtəlif oxşar qaydalar mövcud olmuşdur, lakin onların əsas mahiyyəti eynidir: uçuş marşrutu təyyarəni ən yaxın hava limanından müəyyən maksimum icazə verilən məsafədən çox uzağa apara bilməz. Bu məhdudiyyətlərlə təyyarələr həmişə bir hava limanından digərinə birbaşa marşrutdan istifadə edə bilməzlər.
Bu məsələdə biz iki hava limanı arasında maksimum icazə verilən məsafə qaydasına riayət edərək ən qısa uçuş marşrutunu hesablayacağıq. Aşağıdakı şəkildə, birinci nümunə test vəziyyətini təsvir edən hər hansı bir uçuş marşrutu üç dairə daxilində qalmalıdır. Beləliklə, 2 nömrəli hava limanından 3 nömrəli hava limanına gedən təyyarə 1 nömrəli hava limanı ətrafındakı bölgə vasitəsilə birbaşa marşrutdan kənara çıxmalıdır. Qeyd edək ki, təyyarə mütləq 1 nömrəli hava limanına getməli deyil.
Məsələlər daha da mürəkkəbləşir, çünki təyyarələrin məhdud yanacaq təchizatı var və daha uzun məsafələrə getmək üçün aralıq hava limanlarında dayanmaq lazım ola bilər. Beləliklə, yanacaq tutumundan asılı olaraq, şəkildə 2 nömrəli hava limanından 3 nömrəli hava limanına gedən təyyarə 1 nömrəli hava limanında dayanmalı ola bilər (və ya yanacaq tutumu hətta 1 nömrəli hava limanına getmək üçün çox az ola bilər, bu halda səfər mümkün olmaz).
Aşağıdakı sadələşdirici fərziyyələri edirik:
Yer səthi 6370 km radiuslu bir kürədir.
Həm vaxt, həm də yanacaq sərfiyyatı gedilən məsafə ilə birbaşa mütənasibdir. Başqa sözlə, biz yalnız gedilən ümumi məsafə ilə maraqlanırıq.
Təyyarələrin müxtəlif yüksəkliklərdə uçması ilə yaranan məsafə fərqi əhəmiyyətsizdir. Beləliklə, əslində, onları yer səthi boyunca uçduğunu qəbul edirik.
Təyyarə lazım olduğu qədər aralıq hava limanlarında yanacaq doldurmaq üçün dayana bilər, hər dəfə tam yanacaq alır.
Giriş verilənləri
Hər bir test halının ilk sətri iki tam ədəd N və R ehtiva edir, burada 2 ≤ N ≤ 25 hava limanlarının sayı və 1 ≤ R ≤ 10000 ən yaxın hava limanından icazə verilən maksimum uçuş məsafəsidir (km ilə). Növbəti N sətirin hər biri iki tam ədəd φ, θ ehtiva edir, 0 ≤ φ < 360 və -90 ≤ θ ≤ 90, hava limanının uzunluq və enlik dərəcələrində (müvafiq olaraq). Hava limanları girişdəki sırasına görə birdən başlayaraq nömrələnir. Heç iki hava limanı eyni mövqedə deyil.
Bundan sonra bir tam ədəd Q ehtiva edən bir sətir gəlir, 1 ≤ Q ≤ 100. Növbəti Q sətirin hər biri üç tam ədəd s, t, c ehtiva edir, 1 ≤ s, t ≤ N, s ≠ t, və 1 ≤ c ≤ 50000, s hava limanından t hava limanına gedən və c km məsafə verən yanacaq tutumuna malik təyyarəni göstərir.
Çıxış verilənləri
Hər bir test halı üçün, iş nömrəsini göstərdikdən sonra, yanacaq məhdudiyyəti c nəzərə alınmaqla s və t hava limanları arasında ən qısa uçuş marşrutunun uzunluğunu km ilə göstərən hər bir sorğu üçün bir sətir göstərin. Uzunluğu üç ondalık dəqiqliklə göstərin. İki hava limanı arasında icazə verilən marşrut yoxdursa, əvəzinə impossible sözünü göstərin.
Cavabın R və ya c dəyərlərinin 0.1 km-ə qədər olan dəyişikliklər üçün rəqəmsal olaraq sabit olduğunu qəbul edə bilərsiniz.