Slalom#1257
Madriddə qarın az yağmasına baxmayaraq, şəhərdə qış idman növlərinə, xüsusilə dağ xizəksürməsinə maraq artır. Bir çox insanlar bir neçə həftəsonunu və ya hətta tam həftələri dağlarda bacarıqlarını inkişaf etdirməyə sərf edirlər.
Bu məsələdə biz çoxsaylı alp xizəksürmə növlərindən yalnız birinə — slaloma baxırıq. Tras ardıcıl bir neçə darvaza qoymaqla qurulur; hər darvaza iki ştangadan ibarətdir. Xizəkçi hər darvazanı meydana gətirən iki ştanga arasından keçməlidir. Trasdan ən qısa müddətdə keçən və heç bir darvazanı buraxmayan xizəkçi qalib gəlir.
Siz xizəksürməyə yeni başlamısınız, lakin artıq özünüzə 2018-ci il Qış Olimpiya Oyunlarında iştirak etməyi məqsəd qoymusunuz və Madridin də namizədlik verəcəyi ehtimal olunur. Teorik məşqlərin bir hissəsi kimi, sizə başlanğıc nöqtəsi və ardıcıl bir neçə darvaza verildikdə, yuxarıdan başlayıb bütün darvazalardan növbə ilə keçib sonuncuya (finiş xətti kimi) çatmaq üçün minimal yol uzunluğunu hesablayan bir proqram yazmaq tapşırılır. Darvazaların üfüqi olduğunu və yuxarıdan aşağıya doğru sıralandığını fərz edə bilərsiniz, yəni onları ardıcıllıqla keçməlisiniz. Özünüzü təcrübəli xizəkçi hesab edirsiniz, yəni istənilən ardıcıl dönüşləri edə bilərsiniz və tək narahatlığınız yolun ümumi uzunluğunu minimum etməkdir.
Hər bir test üçün ilk sətirdə darvazaların sayı (1 \le n \le 1000) verilir. Sonra bir sətirdə başlanğıc mövqeyinin Kartesi koordinatları olan iki onluq ədəd — əvvəlcə , sonra gəlir. Növbəti sətirdə hər birində üç onluq ədəd olan y\ x_1\ x_2 göstərilir, bu da növbəti darvazanı (x_1, y) nöqtəsindən (x_2, y) nöqtəsinədək olan üfüqi xətt kimi müəyyən edir. x_1 < x_2 olduğunu təhlükəsiz qəbul edə bilərsiniz. qiymətləri ciddi şəkildə azalan ardıcıllıq təşkil edir və həmişə başlanğıc mövqeyinin -dəyərindən kiçikdir. Sonuncu darvaza finiş xəttidir. Bütün koordinatlar və aralığındadır (hər iki sərhəd daxil olmaqla). n=0 olduqda giriş bitmiş hesab olunur. Hər bir testdən sonra boş sətir gəlir.
Hər test üçün finiş xəttinə çatmaq üçün tələb olunan minimal məsafəni bir sətirdə çap edin. Cavabınızın 10^{-7} dəqiqliklə (fərq və ya nisbətən) düzgün olduğunu təmin edin.
Nümunə 1