Uçuş Yolu
Klub, köhnəlmiş nəqliyyat vasitələrinin mayın 5-də, 5555-ci ildə qədim təyyarələrin nüsxələrinin böyük uçuşları ilə qeyd olunmasına qərar verdi. Klub üzvləri Yer səthində müxtəlif yerlərdə N (2 ≤ N ≤ 1000) aerodromlar tikmiş və təyyarələr hazırlamışlar. Lakin qəfildən ekoloji vergilər qanununa dəyişiklik edildi və bu səbəbdən klub bayramları qısa formatda keçirməlidir. İki aerodrom seçildi və yalnız bir təyyarə onların arasında ən qısa yolla uçacaq! Təyyarənin eniş etmədən uça biləcəyi maksimum məsafə R km-dir, buna görə də lazım gələrsə, aralıq aerodromlardan istifadə edə bilər.
Kluba başlanğıcdan sona qədər ən qısa marşrutu tapmaqda kömək edin, Yer səthini tam dəqiq kürə kimi qəbul edərək, ekvator uzunluğu dəqiq 40000 km və uçuş hündürlüyünün məsafəyə təsirini nəzərə almadan.
Giriş verilənləri
Girişin ilk sətiri R – maksimum birbaşa uçuş məsafəsini (kilometrlə, 10 ≤ R ≤ 50000) ehtiva edir. İkinci sətir aerodromların sayını N ehtiva edir. Növbəti N sətir aerodromların coğrafi koordinatlarını ehtiva edir. Koordinatların formatı belədir: əvvəlcə enlik (böyük hərflə N və ya S — Şimal və ya Cənub, sonra dərəcə, dəqiqə və saniyə), sonra uzunluq (oxşar, lakin E və ya W — Şərq və ya Qərb hərfləri istifadə olunur), bütün rəqəmlər və hərflər tək boşluqla ayrılır. Girişin son sətirində başlanğıc və son olaraq seçilmiş aerodromları göstərən iki tam ədəd (1-dən başlayaraq, yəni nömrələmə 1-dən başlayır) var.
Çıxış verilənləri
Proqramınız üç sətir çıxarmalıdır. 1-ci sətir başlanğıcdan sona qədər marşrutun mümkün olan minimal uzunluğunu, kilometrdə, metrlərə qədər dəqiqliklə göstərən bir ondalık dəyər ehtiva etməlidir. 2-ci sətir dəqiq bir tam ədəd K – marşrutdakı aralıq aerodromların sayını ehtiva etməlidir. 3-cü sətir bu aralıq aerodromların siyahısını, başlanğıcdan sona qədər ardıcıllıqla ehtiva etməlidir. Əgər müxtəlif düzgün cavablar varsa, proqramınız onlardan birini tapmalıdır. Əgər təyyarə eniş etmədən başlanğıcdan sona çata bilirsə, 2-ci sətir 0 ehtiva etməli və 3-cü sətir boş olmalıdır. Əgər təyyarə başlanğıcdan sona çata bilmirsə, 1-ci sətir 123456789.000 rəqəmini, 2-ci sətir 0 rəqəmini ehtiva etməli və 3-cü sətir boş olmalıdır.