Формула 42#8719

Формула 42

1 секунда

128 мегабайтів

Складна

Для проведення гран-прі Флатландії планується збудувати нову трасу Формули 42. Відомий проектувальник трас Герман Кількін розробив креслення траси. Однак, після початку будівництва виявилася невелика проблема з проектом.

Траса Формули 42 — це територія, обмежена з двох боків бар'єрами. Кожен бар'єр є замкненою ламаною, що утворює межу опуклого багатокутника. Внутрішній бар'єр повністю розташований всередині зовнішнього і не має з ним спільних точок. Болід Формули 42 має форму кола. Радіус кола не регламентований, і вважається, що змагання стають видовищнішими, чим більший радіус боліда.

Проблема в проекті полягає в тому, що Герман зобразив на кресленні окремо форму зовнішнього бар'єра і окремо — форму внутрішнього, не вказавши їх взаємне розташування. Тепер будівельники можуть вибрати довільне взаємне розташування бар'єрів. Вони прагнуть розташувати бар'єри так, щоб гонка була максимально видовищною. Кожен з бар'єрів можна переміщати паралельним перенесенням, але не можна повертати, відображати або іншим чином змінювати.

Необхідно вибрати таке взаємне розташування бар'єрів, щоб отриману трасу можна було використовувати для гонки з максимальним розміром гоночного боліда. Трасу можна використовувати з болідом радіуса $r$ , якщо болід такого радіуса, перебуваючи на трасі, може здійснити повне коло навколо внутрішнього бар'єра. У процесі руху жодна точка боліда не повинна опинятися строго всередині внутрішнього бар'єра або строго зовні від зовнішнього бар'єра. Дотики до бар'єрів дозволяються. Формально: для точки $P$ всередині замкненого бар'єра існує така неперервна замкнена крива, що точка $P$ лежить всередині цієї кривої, і для будь-якої точки цієї кривої коло з радіусом $r$ з центром у цій точці лежить всередині зовнішнього бар'єра і зовні від внутрішнього бар'єра, дотики дозволяються.

Допоможіть розібратися з планом Германа і визначити, для якого максимального радіуса гоночного боліда можливо побудувати трасу відповідно до наявних креслень зовнішнього і внутрішнього бар'єрів.

Вхідні дані

Містять опис двох багатокутників, межі яких задають форми зовнішнього і внутрішнього бар'єрів, відповідно.

У першому рядку знаходиться ціле число $n$ ( $3 \leq n \leq 100$ 3 \le n \le 100) - кількість вершин у першому багатокутнику. У наступних $n$ рядках дано по два цілих числа $x_{i}$ x_i і $y_{i}$ y_i ( $0 \leq x_{i}, y_{i} \leq 1000$ 0 \le x_i, y_i \le 1000) - координати вершин першого багатокутника.

У наступному рядку знаходиться ціле число $m$ ( $3 \leq m \leq 100$ 3 \le m \le 100) - кількість вершин у другому багатокутнику. У наступних $m$ рядках дано по два цілих числа $x_{i}^{'}$ x_i' і $y_{i}^{'}$ y_i' - координати вершин другого багатокутника ( $0 \leq x_{i}^{'}, y_{i}^{'} \leq 1000$ 0 \le x_i', y_i' \le 1000).

Вершини кожного багатокутника задані в порядку обходу проти годинникової стрілки. Багатокутники є опуклими, жодні три вершини одного багатокутника не лежать на одній прямій. Гарантується, що можна здійснити паралельне перенесення багатокутників таким чином, що другий опиниться строго всередині першого, і їх межі не матимуть спільних точок.

Вихідні дані

Виведіть одне число - максимальний радіус боліда. Відповідь буде вважатися правильною, якщо його абсолютна або відносна похибка не перевищує $1 0^{- 6}$ 10^{-6}.

Приклади

Приклад 1

Приклад 2