Круглий острів#1924

Круглий острів

6 секунд

256 мегабайтів

Дуже складна

Андрій зробив значне відкриття в географії: він знайшов острів, який раніше не був відомий цивілізованому світу. Цей острів має ідеальну круглу форму і населений двома племенами: Java та Seeplusplus. Після короткого контакту з аборигенами Андрій дізнався, що межа між землями племен проходить по прямій лінії. Більше того, він знає розташування кількох селищ Java та кількох селищ Seeplusplus (кожне селище, звісно, знаходиться всередині або на межі території відповідного племені). Тепер йому потрібно визначити мінімальну і максимальну можливу площу земель Java. Допоможіть йому!

Вхідні дані

Перший рядок містить ціле число $r$ — радіус острова ( $1 \leq r \leq 1 0^{9}$ 1 \le r \le 10^9). Наступний рядок містить ціле число $n$ ( $1 \leq n \leq 50000$ 1 \le n \le 50000) — кількість селищ Java. Кожен з наступних $n$ рядків містить два цілі числа $x$ та $y$ — координати селищ Java. Далі йде рядок з цілим числом $m$ ( $1 \leq m \leq 50000$ 1 \le m \le 50000) — кількість селищ Seeplusplus. Кожен з наступних $m$ рядків містить два цілі числа $x$ та $y$ — координати селищ Seeplusplus. Центр острова має координати $(0, 0)$ , кожне селище знаходиться в межах острова і принаймні на відстані $r /10$ від його межі. Жодні два селища не збігаються. Гарантується коректність вхідних даних: завжди існуватиме хоча б одна пряма, що розділяє селища Java та Seeplusplus.

Вихідні дані

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

Приклади

Приклад 1