Ətraf Mühitin Mühafizəsi
Arsenik və Sianid Mədənçiliyi (ACM) adlı şirkət, yaxınlıqdakı şəhərinizin torpaqlarında mədən işlərinə başlamağı planlaşdırır. Siz, vətəndaşların tənzimləyici komitəsinin üzvü olaraq, ətraf mühiti və yerli sakinlərin sağlamlığını qurban vermədən, iş yerlərini və digər faydaları qoruyaraq, şirkətin bu torpaqlardan nə qədər mədən çıxara biləcəyini nəzarət etməlisiniz.
ACM bir neçə düzbucaqlı torpaq sahəsini mədən etmək istəyir. Bir torpaq sahəsinin eni W, maksimum dərinliyi isə D ola bilər və səthi 0 dərinliyində hesab olunur. Hər bir sahədəki minerallar üç təbəqədə təşkil olunub və bu təbəqələr sahənin eni boyunca dərinlikdə dəyişə bilər, amma həmişə bütün uzunluğu boyunca eyni profildədir. Buna görə də ACM yalnız hər bir sahənin eni boyunca olan profil ilə maraqlanır və onun formasını dəqiq müəyyən etmək üçün kəşfiyyat işləri aparmışdır. Nəticədə, üç təbəqə arasındakı iki interfeysin y_1(x) və y_2(x) funksiyaları ilə təmsil oluna biləcəyini aşkar etdilər. Burada birincisi üst təbəqə ilə orta təbəqə arasındakı sərhədi, ikincisi isə orta təbəqə ilə alt təbəqə arasındakı sərhədi təsvir edir. Bu funksiyalar həmişə belədir ki,
-D < y_2(x) < y_1(x) < 0 üçün 0 ≤ x ≤ W,
belə ki, təbəqələrin sərhədləri heç vaxt bir-birinə toxunmur. Bundan əlavə, hər bir funksiyanın forması y_i(x) = p_i(x)/q_i(x) şəklindədir, burada
və ,
üçün i = 1, 2 və müəyyən bir tam ədəd K. Aşağıdakı şəkil ACM-nin onları təmsil etdiyi şəkildə iki torpaq sahəsinin profillərini göstərir. Soldakı sahənin eni W=6 və dərinliyi D=9, sağdakı sahənin isə W=8 və D=10. Hər bir sahənin təbəqələrinin sərhədləri onların altında müəyyən edilmiş funksiyalarla təsvir olunur.
ACM bir torpaq sahəsində müəyyən bir qazma dərinliyinə qədər hər şeyi qazacaq və sonra əldə olunan bütün mineralları sataraq mənfəət əldə edəcək. Lakin, üst və alt təbəqələrdəki minerallar əslində dəyərsizdir, buna görə də bütün əməliyyatın mənfəəti yalnız orta təbəqədəki minerallardan gəlir. Əslində, mənfəət profilin ən çox d dərinliyində olan orta təbəqənin sahəsi A ilə mütənasibdir. Bir torpaq sahəsinin təsviri və tam ədəd A verildikdə, ACM-nin profilin orta təbəqəsindən dəqiq A sahəsi alması üçün torpaq sahəsini qazmasına icazə verməli olduğunuz qazma dərinliyi d bilmək istəyirsiniz. Yuxarıdakı şəkildə nümunə girişindəki iki test üçün cavabı görə bilərsiniz. Soldakı sahə üçün A=4 sahəsi əldə etmək üçün qazma dərinliyi d=4.00000 olmalıdır, sağdakı sahə üçün isə A=14 sahəsi d=5.51389 qazma dərinliyi tələb edir.
Giriş verilənləri
Hər bir test beş sətirdən istifadə edərək təsvir olunur. Birinci sətir dörd tam ədəd W, D, A və K ehtiva edir, burada W ACM-nin mədən etmək istədiyi torpaq sahəsinin eni (1 ≤ W ≤ 8), D onun dərinliyidir (1 ≤ D ≤ 10), A ACM-nin əldə etməli olduğu profilin orta təbəqəsinin sahəsidir (1 ≤ A ≤ W×D), və K interfeyslərin y_1(x) və y_2(x) olaraq müəyyən edilməsinə imkan verir (0 ≤ K ≤ 8). Digər sətirlər K+1 arasında olan -10^8 və 10^8 daxil olmaqla tam ədədlərdən ibarətdir. İkinci sətir p_1(x)-in P_{1,0}-dən P_{1,K}-ə qədər olan əmsallarını ehtiva edir. Üçüncü sətir q_1(x)-in Q_{1,0}-dən Q_{1,K}-ə qədər olan əmsallarını ehtiva edir. Dördüncü sətir p_2(x)-in P_{2,0}-dən P_{2,K}-ə qədər olan əmsallarını ehtiva edir. Beşinci sətir q_2(x)-in Q_{2,0}-dən Q_{2,K}-ə qədər olan əmsallarını ehtiva edir. Hər bir test daxilində A profilin orta təbəqəsinin ümumi sahəsindən ciddi şəkildə azdır və elə bir d dəyəri mövcuddur ki, qazma dərinliyi d profilin orta təbəqəsindən dəqiq A sahəsi verir. Bundan əlavə, q_1(x)=0, q_2(x)=0 və -D < y_2(x) < y_1(x) < 0, üçün 0 ≤ x ≤ W.
Çıxış verilənləri
Hər bir test üçün bir sətir çıxış edin, burada ACM-nin torpaq sahəsini qazmasına icazə verilməli olan dərinliyi d təmsil edən rasional bir ədəd var ki, onlar profilin orta təbəqəsindən dəqiq A sahəsi əldə etsinlər. Nəticə zəruri hallarda yuvarlaqlaşdırılaraq, ondalık nöqtədən sonra dəqiq beş rəqəm ilə rasional bir ədəd kimi çıxarılmalıdır.