Son Zamanlar Fjord Sürmüsünüzmü?
Çoxumuzun bildiyi kimi, qərbi Skandinaviya sahil xətti dənizdən gələn çoxlu kiçik körfəzlərə malikdir ki, bunlar fjordlar kimi tanınır. Fjordların çox dik tərəfləri var və sahil boyunca səyahət etməyi bir qədər yorucu (lakin nəfəs kəsici) edir, çünki yollar onların ətrafında dönməlidir. Fjord Sürətləndirilmiş Skandinaviya Trafik Komissiyası (FAST) bu problemi fjordlar üzərində bir sıra körpülər inşa edərək həll etməyə qərar verib ki, bu da səyahət edilməli olan məsafələri azaldacaq. Xərcləri azaltmaq üçün FAST hər biri 1 metr uzunluğunda əvvəlcədən hazırlanmış körpü vahidlərindən istifadə edir, lakin maliyyə məhdudiyyətləri səbəbindən inşa edə biləcəkləri körpünün ümumi uzunluğu məhduddur. Buna görə də, yolların ən çox uzunluğunu qənaət edəcək optimal körpü yerləşdirmə yerlərini müəyyən etmək istəyirlər. Məsələn, əgər 10 metr uzunluğunda bir körpü tikilərsə və bu, köhnə yolun 30 metrini kəsərsə, 20 metr qənaət edilir. Körpülərin harada yerləşdiriləcəyini sadələşdirmək üçün FAST hər fjordu aşağıda göstərilən şəkildə üç nöqtəni birləşdirən iki xətt seqmenti kimi modelləşdirməyə qərar verib.
Əlbəttə ki, fjordları əmələ gətirən bütün bucaqlar 180°-dən kiçikdir. Bundan əlavə, təhlükəsizlik səbəblərinə görə hər körpü ən çox bir fjordu əhatə edə bilər.
Giriş verilənləri
Hər test üçün giriş iki sətirdən ibarət olacaq. Birinci sətir fjordların sayı və tikilə biləcək körpünün maksimum uzunluğunu (metrlə) göstərən iki müsbət tam ədəd n və m ehtiva edir. Növbəti sətir fjordlar üçün 2n+1 cüt tam ədəd koordinatları ehtiva edəcək, burada fjord i üçün son koordinat fjord i+1 üçün ilk koordinat kimi xidmət edir. Bütün koordinatlar metrlə verilir və -300000 ilə 300000 arasında olacaq. n və m üçün maksimum dəyərlər müvafiq olaraq 50 və 3000-dir.
Giriş 0 0 sətiri ilə bitəcək.
Çıxış verilənləri
Hər test üçün körpünün istifadə olunan uzunluğu və körpülərin optimal yerləşdirilməsi üçün ümumi qənaəti göstərən bir sətir çıxarın, aşağıda göstərilən formatdan istifadə edin. Bütün dəyərlər metrlə olmalıdır və sonuncu rəqəmi ən yaxın yüzdə birə yuvarlayın.