Sürmə Təlimatları
Populyar inanca zidd olaraq, yadplanetli uçan boşqablar Yer planetimizin ətrafında istənilən şəkildə uça bilməzlər. Onların eniş və qalxma manevrləri çox enerji tələb edir, buna görə də onlar Yerə missiyalarını diqqətlə planlaşdırırlar ki, bir konkret yerdə eniş etsinlər, sonra missiyalarını yerinə yetirərək yerin üstündə dayansınlar və sonra qalxsınlar. İnsan sivilizasiyası hələ inkişaf etmədiyi zamanlarda bu çox asan idi, çünki uçan boşqablar bütün ağacların və binaların üstündə dayana bilərdi və bir missiya nöqtəsindən digərinə ən qısa yol adətən sadə bir düz xətt idi — səyahət etmək üçün ən səmərəli yol. Lakin müasir şəhərlərdə göydələnlər o qədər hündürdür ki, uçan boşqablar onların üstündə dayana bilmir və müasir şəhərdə naviqasiya etmək vəzifəsi olduqca mürəkkəb bir işə çevrilib. Siz yadplanetli bir casus tərəfindən şəhər boyunca uçan boşqablara sürücülük istiqamətləri verəcək bir proqram yazmaq üçün işə götürüldünüz. İlk tapşırığınız olaraq (yadplanetli ustalarınıza dəyərinizi sübut etmək üçün) uçan boşqabın bir nöqtədən digərinə ən qısa məsafəni hesablayan bir proqram yazmalısınız. Bu proqram yadplanetlilər tərəfindən missiya enerji tələblərinin planlaşdırılmasında köməkçi olaraq istifadə olunacaq.
Problem bir neçə faktla sadələşdirilib. İlk növbədə, uçan boşqab əksər binaların üstündə dayana bildiyi üçün yalnız göydələnlərin yerləri ilə maraqlanırsınız. İkincisi, problem əslində iki ölçülüdür — hər şeyi "yuxarıdan" baxaraq təsəvvür edə bilərsiniz və bütün obyektlərin OXY Kartezyen müstəvisində yerləşdiyini düşünə bilərsiniz. Uçan boşqab radiusu r olan bir dairə ilə təmsil olunur və müasir şəhərlər göydələnlərlə nizamlı olduğundan, hər bir göydələn OX və OY oxlarına paralel olan bir düzbucaqlı ilə təmsil olunur.
Tərifə görə, uçan boşqabın yeri onun mərkəzinin yeridir və onun keçdiyi yolun uzunluğu mərkəzinin keçdiyi yolun uzunluğudur. Missiyası zamanı uçan boşqab göydələnlərə toxuna bilər, lakin onları kəsə bilməz.
Birinci şəkildə r = 1 olan bir uçan boşqab A nöqtəsindən B nöqtəsinə getməlidir. Göydələn 1 olmasaydı, düz xətli kəsikli xətt ən qısa yol olardı. Göydələn 1-dən qaçmaq üçün ən qısa yol onun yuxarı sağ küncündən keçməkdir, lakin göydələn 2 oradan uçmaq üçün çox yaxındır. Beləliklə, cavab göydələn 1-in aşağı sol küncündən keçərək ümumi yol uzunluğu 10.570796 olur.
İkinci şəkildə r = 2 olan bir uçan boşqabın A nöqtəsindən B nöqtəsinə getməsi mümkün deyil, çünki bütün göydələnlər arasında uçmaq üçün çox yaxındır.
Üçüncü şəkildə r = 1 olan bir uçan boşqab ən qısa yol olan 11.652892 uzunluğunda A və B arasında iki göydələn ətrafında slalom kimi uçmalıdır.
Giriş verilənləri
Girişin ilk sətiri tam ədədlər r və n (1 ≤ r ≤ 100, 0 ≤ n ≤ 30) ehtiva edir, burada r uçan boşqabın radiusudur və n göydələnlərin sayıdır. Növbəti sətir dörd tam ədəd x_A, y_A, x_B və y_B (-1000 ≤ x_A, y_A, x_B, y_B ≤ 1000) ehtiva edir, burada (x_A, y_A) uçan boşqabın missiyasının başlanğıc nöqtəsinin koordinatlarıdır və (x_B, y_B) onun bitmə nöqtəsinin koordinatlarıdır.
Növbəti n sətir göydələnləri təsvir edir. Hər bir göydələn dörd tam ədəd x_1, y_1, x_2 və y_2 (-1000 ≤ x_1, y_1, x_2, y_2 ≤ 1000, x_1 < x_2, y_1 < y_2) ilə təmsil olunur — müvafiq düzbucaqlının künclərinin koordinatları.
Göydələnlər bir-birini kəsmir və ya toxunmur. Uçan boşqabın missiyasının başlanğıc və bitmə nöqtələri uçan boşqab üçün etibarlı yerlərdir, yəni bu nöqtələrdə heç bir göydələnlə kəsişmir, lakin bəzilərinə toxuna bilər.
Çıxış verilənləri
Əgər uçan boşqab başlanğıc nöqtəsindən bitmə nöqtəsinə çata bilmirsə, çıxışa "no solution" (tırnaq işarələri olmadan) mətnini yazın. Əks halda, çıxışa tək bir ədəd yazın — uçan boşqabın başlanğıc nöqtəsindən bitmə nöqtəsinə çatmaq üçün keçməsi lazım olan ən qısa məsafə. Cavab ən azı ondalık nöqtədən sonra 6 rəqəm dəqiqliyində olmalıdır.