8810번 - Studnia 다국어

Pan Michał chce wykopać nową studnię. Dysponuje planem terenu swojej działki, na którym przedstawione są dwa zarysy: powierzchni gruntu oraz początku warstwy wodonośnej, które mają kształt linii łamanych. Pan Michał wynajął już specjalne wiertło, które może wiercić jedynie w pionie. Koszty wiercenia są całkiem spore, nic dziwnego więc, że zastanawia się, na jaką głębokość co najmniej musi wykonać odwiert, by dotrzeć z powierzchni do warstwy wodonośnej.

W pierwszej linii znajduje się jedna liczba naturalna Z ( 1 <= Z <= 5 ) oznaczająca liczbę zestawów testowych. Następnie opisywane są kolejne zestawy.

W pierwszej linii znajduje się jedna liczba naturalna n ( 2 <= n <= 100 000 ), oznaczająca liczbę punktów łamanej opisującej powierzchnię gruntu na działce pana Michała. W drugim wierszu występuje n par liczb naturalnych x_i, y_i ( 1 <= x_i, y_i <= 10⁹ ), pooddzielanych pojedynczymi odstępami. Dla każdego 1 <= i < n zachodzi: x_i < x_i+1.

W kolejnych dwóch liniach znajduje się analogiczny opis łamanej opisującej początek warstwy wodonośnej pod działką pana Michała. W pierwszej z nich znajduje się liczba naturalna m ( 2 <= m < n+m <= 100 000 ), oznaczająca liczbę punktów, a w drugiej z linii jest m par liczb naturalnych u_i, v_i ( 1 <= u_i, v_i <= 10⁹ ), pooddzielanych pojedynczymi odstępami. Dla każdego 1 <= i < m zachodzi: u_i < u_i+1.

Warstwa wodonośna znajduje się w całości pod powierzchnią gruntu ( te dwie łamane nie mają punktów wspólnych ). Ponadto zachodzą równości: x₁ = u₁ oraz x_n = u_m.

Dla każdego zestawu testowego w osobnej linii należy wypisać jedną liczbę rzeczywistą dodatnią - minimalną głębokość dzielącą powierzchnię od warstwy wodonośnej. Wartość tę należy zaokrąglić do dokładnie dwóch miejsc po przecinku.

W pierwszym teście na całej długości działki szukana różnica głębokości wynosi 1.

W drugim teście różnica jest najmniejsza w punkcie x = 5, i jest tam równa dokładnie 2.

W trzecim teście różnica jest najmniejsza w punkcie x = 10.