Son Zamanlar Fjord Sürmüsünüzmü?#2681
Çoxumuzun bildiyi kimi, Skandinaviyanın qərb sahilində dənizdən çoxlu kiçik girişlər – fyordlar yerləşir. Fyordların yamacları çox sıldırımlı olduğundan, sahil boyunca səyahət etmək bir qədər çətin (lakin valehedici) olur, çünki yollar onların ətrafında dolaşmalıdır. Fyordların Sürətli Skandinaviyada Nəqliyyat Komissiyası (FAST) bu problemi fyordlar üzərində körpülər tikməklə, səyahət məsafələrini azaltmağı qərara alıb. Xərclərə qənaət etmək üçün FAST əvvəlcədən hazırlanmış, hər biri metr uzunluğunda olan körpü bloklarından istifadə edir, lakin maliyyə məhdudiyyətlərinə görə tikilə biləcək körpünün ümumi uzunluğu məhduddur. Buna görə də, onlar bütün yollar üzrə qənaəti maksimum etmək üçün körpülərin optimal yerlərdə quraşdırılmasını müəyyən etmək istəyirlər. Məsələn, əgər metr uzunluğunda körpü tikilərsə və bu, köhnə yolun metrinin yolunu qısaldarsa, ümumilikdə metr qənaət edilir. Körpülərin yerləşdirilməsini sadələşdirmək üçün FAST hər fyordu şəkildəki kimi üç nöqtəni birləşdirən iki düz xətt parçası kimi modelləşdirib.
Bütün fyordları təşkil edən bucaqlar 180^{\circ}-dan kiçikdir. Təhlükəsizlik baxımından hər bir körpü ən çox bir fyordu keçə bilər.
Hər test üçün giriş iki sətirdən ibarətdir. Birinci sətirdə və – fyordların sayı və tikilə bilən maksimum körpü uzunluğu (metrlə) verilmişdir. Növbəti sətirdə isə fyordlar üçün 2n+1 ədəd tam ədəddən ibarət koordinat cütləri verilmişdir, burada -ci fyord üçün sonuncu koordinat növbəti (i+1)-ci fyord üçün birinci koordinat olaraq çıxış edir. Bütün koordinatlar metrlə verilir və ilə arasında dəyişir. və -in maksimum dəyərləri müvafiq olaraq və -dir.
Giriş, sətiri ilə tamamlanır.
Hər test üçün bir sətirdə testin nömrəsini, istifadə olunmuş ümumi körpü uzunluğunu və körpülərin optimal yerləşdirilməsi zamanı əldə edilmiş ümumi qənaəti aşağıdakı formada çıxışa verin. Bütün dəyərlər metrlə olmalıdır və qənaət məbləği ən yaxın yüzdə birə qədər yuvarlaqlaşdırılmalıdır.
Nümunə 1