З'єднані гіфи#5043

З'єднані гіфи

1 секунда

64 мегабайти

Складна

Гіфи (множина від гіф) — це об'єкти, схожі на воронки. Визначимо гіф як двовимірний об'єкт, заданий послідовністю точок $p_{1}, p_{2}, \dots, p_{n}$ p_1, p_2, \ldots, p_n з такими властивостями:

$3 \leq n \leq 1000$ 3 \leq n \leq 1000.
Якщо точка $p_{i}$ p_i має координати $(x_{i}, y_{i})$ (x_i, y_i), то існує індекс $c$ з $1 < c < n$ 1 < c < n такий, що $y_{1} > y_{2} > \dots > y_{c}$ y_1 > y_2 > \ldots > y_c і $y_{c} < y_{c + 1} < y_{c + 2} < \dots < y_{n}$ y_c < y_{c+1} < y_{c+2} < \ldots < y_n. Точка $p_{c}$ p_c називається виступом гіфа.
Для всіх $1 \leq i < c$ 1 \leq i < c маємо $x_{i} < x_{c}$ x_i < x_c; для всіх $c < i \leq n$ c < i \leq n маємо $x_{i} > x_{c}$ x_i > x_c.
Для $1 < i < c$ 1 < i < c кут, на який $p_{i - 1}$ p_{i-1} потрібно повернути навколо $p_{i}$ p_i за годинниковою стрілкою, щоб стати колінеарним з $p_{i}$ p_i і $p_{i + 1}$ p_{i+1}, більший за $180$ градусів. Аналогічно, для $c < i < n$ c < i < n потрібний кут для $p_{i - 1}$ p_{i-1}, щоб стати колінеарним з $p_{i}$ p_i і $p_{i + 1}$ p_{i+1} (при обертанні навколо $p_{i}$ p_i за годинниковою стрілкою), також більший за $180$ градусів.
Відрізки, що з'єднують кожні дві сусідні точки $p_{i}$ p_i та $p_{i + 1}$ p_{i+1}, перетинаються лише у своїх кінцях.

Наприклад, на наступному рисунку зображено гіф з шести точок та $c = 4$ c = 4:

Послідовність відрізків $p_{1} p_{2}, p_{2} p_{3}, \dots, p_{n - 1} p_{n}$ p_1p_2, p_2p_3, \ldots, p_{n-1}p_n назвемо тілом гіфа. У цій задачі дано два гіфи $P = (p_{1}, p_{2}, \dots, p_{n})$ P = (p_1, p_2, \ldots, p_n) та $Q = (q_{1}, q_{2}, \dots, q_{m})$ Q = (q_1, q_2, \ldots, q_m), такі що всі $x$ -координати $p_{i}$ p_i — від'ємні цілі числа, а всі $x$ -координати $q_{i}$ q_i — додатні цілі числа.

Вважаємо, що виступи двох гіфів з'єднані тонкою трубкою. У цю систему наливають воду; під час наповнення гіфи заповнюються згідно з основними фізичними законами (рівень води в обох гіфах залишається однаковим). Коли рівень води у $P$ досягає $min (y_{1}, y_{n})$ \min(y_1, y_n), вода починає виливатися з $P$ (аналогічно і для $Q$ ).

Визначте кінцевий рівень води в гіфах після залиття заданої кількості води. Оскільки задача розглядається у двовимірному просторі, об'єм води вимірюється площею, яку вона займає. Об'єм з'єднувальної трубки вважати нульовим.

Вхідні дані

Перший рядок містить кількість тестів $t$ . Кожен тест складається з трьох рядків. Перший з цих трьох рядків містить ціле число $a$ ( $1 \leq a \leq 100000$ 1 \leq a \leq 100000) — кількість налитої води. Наступні два рядки задають $P$ та $Q$ . Кожен гіф подається у форматі $k$ $x_{1} y_{1} x_{2} y_{2} \dots x_{k} y_{k}$ x_1 y_1 x_2 y_2 \ldots x_k y_k, де $k$ — кількість точок у гіфі (для $P$ — $n$ , для $Q$ — $m$ ), а $x_{i}, y_{i}$ x_i, y_i — координати точок у послідовності.

Вихідні дані

Вивести $t$ рядків — у кожному з них одне число $L$ : кінцевий рівень води, виражений в одиницях $y$ -координати, округлений до трьох знаків після коми.

Приклади

Приклад 1