Захист довкілля#6599

Захист довкілля

5 секунд

64 мегабайти

Складна

Видобуток миш'яку та ціаніду (ACM) — це корпорація, яка нещодавно вирішила почати розробку своїх шахт на землях поблизу вашого рідного міста. Як член комітету громадського контролю за роботою ACM, ваше завдання полягає в тому, щоб контролювати, скільки корпорація може видобувати з цих земель, щоб зберегти робочі місця та інші переваги, не жертвуючи навколишнім середовищем і здоров'ям місцевих жителів.

ACM планує видобувати кілька прямокутних земельних ділянок. Земельна ділянка має ширину $W$ , може бути викопана до максимальної глибини $D$ , і має рівну поверхню, яку ми вважаємо на глибині $0$ . Мінерали на земельній ділянці організовані в три шари, які можуть змінювати свою глибину вздовж ширини ділянки, але завжди мають однаковий профіль уздовж всієї її довжини. Саме тому ACM цікавиться лише профілем вздовж ширини кожної ділянки і провела дослідницькі роботи, щоб точно визначити його форму. В результаті вони виявили, що дві межі між трьома шарами мінералів можуть бути представлені двома функціями $y_{1} (x)$ y_1(x) та $y_{2} (x)$ y_2(x), де перша описує межу між верхнім і середнім шаром, а друга — межу між середнім і нижнім шаром. Ці функції завжди такі, що

$- D < y_{2} (x) < y_{1} (x) < 0$ -D < y_2(x) < y_1(x) < 0 для $0 \leq x \leq W$ 0 \le x \le W,

так що межі шарів ніколи не торкаються одна одної. Крім того, кожна функція має вигляд $y_{i} (x) = p_{i} (x) / q_{i} (x)$ y_i(x) = p_i(x)/q_i(x), де

і ,

для $i = 1$ i = 1, $2$ та певного цілого числа $K$ . На малюнку нижче показані профілі двох земельних ділянок так, як їх представляє ACM. Ділянка зліва має ширину $W = 6$ W=6 і глибину $D = 9$ D=9, тоді як ділянка справа має $W = 8$ W=8 і $D = 10$ D=10. Межі шарів кожної ділянки описуються функціями, визначеними під ними.

ACM викопає все на земельній ділянці до певної глибини копання $d$ , а потім продасть усі отримані мінерали, щоб отримати прибуток. Однак мінерали у верхньому та нижньому шарах фактично не мають цінності, тому прибуток від усієї операції надходить виключно від мінералів у середньому шарі. Насправді прибуток пропорційний площі $A$ середнього шару в профілі, який знаходиться на глибині не більше $d$ . Враховуючи опис земельної ділянки та ціле число $A$ , ви хотіли б знати глибину копання $d$ , до якої ви повинні дозволити ACM копати на ділянці, щоб вони отримали площу мінералів із середнього шару в профілі точно $A$ . На малюнку вище ви можете побачити відповідь для двох тестових випадків у прикладі введення. Для ділянки зліва, щоб отримати площу $A = 4$ A=4, глибина копання повинна бути $d = 4.00000$ d=4.00000, тоді як для ділянки справа площа $A = 14$ A=14 вимагає глибини копання $d = 5.51389$ d=5.51389.

Вхідні дані

Кожен тестовий випадок описується за допомогою п'яти рядків. Перший рядок містить чотири цілі числа $W$ , $D$ , $A$ та $K$ , де $W$ — це ширина земельної ділянки, яку ACM хоче видобувати ( $1 \leq W \leq 8$ 1 \le W \le 8), $D$ — її глибина ( $1 \leq D \leq 10$ 1 \le D \le 10), $A$ — це площа середнього шару в профілі, яку ACM повинна отримати ( $1 \leq A \leq W \times D$ 1 \le A \le W \times D), а $K$ дозволяє визначити межі $y_{1} (x)$ y_1(x) та $y_{2} (x)$ y_2(x), як пояснено вище ( $0 \leq K \leq 8$ 0 \le K \le 8). Кожен з інших рядків містить $K + 1$ K+1 цілих чисел від $- 1 0^{8}$ -10^8 до $1 0^{8}$ 10^8 включно. Другий рядок містить коефіцієнти $p_{1} (x)$ p_1(x) від $P_{1, 0}$ P_{1,0} до $P_{1, K}$ P_{1,K}. Третій рядок містить коефіцієнти $q_{1} (x)$ q_1(x) від $Q_{1, 0}$ Q_{1,0} до $Q_{1, K}$ Q_{1,K}. Четвертий рядок містить коефіцієнти $p_{2} (x)$ p_2(x) від $P_{2, 0}$ P_{2,0} до $P_{2, K}$ P_{2,K}. П'ятий рядок містить коефіцієнти $q_{2} (x)$ q_2(x) від $Q_{2, 0}$ Q_{2,0} до $Q_{2, K}$ Q_{2,K}. У межах кожного тестового випадку $A$ строго менше загальної площі середнього шару в профілі, і існує єдине значення $d$ , таке що глибина копання $d$ дає площу мінералів із середнього шару в профілі точно $A$ . Крім того, $q_{1} (x) \neq = 0$ q_1(x)\ne0, $q_{2} (x) \neq = 0$ q_2(x)\ne0 і $- D < y_{2} (x) < y_{1} (x) < 0$ -D < y_2(x) < y_1(x) < 0, для $0 \leq x \leq W$ 0 \le x \le W.

Вихідні дані

Для кожного тестового випадку виведіть рядок з раціональним числом, що представляє глибину $d$ , до якої ACM слід дозволити копати земельну ділянку, щоб вони отримали площу мінералів із середнього шару в профілі точно $A$ . Результат повинен бути виведений як раціональне число рівно з п’ятьма знаками після десяткової крапки, округлене в разі необхідності.

Приклади

Приклад 1