eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Circular Island

Circular Island

Лимит времени 6 секунд
Лимит использования памяти 256 MiB

Andrew has just made a breakthrough in geography: he has found an island that was previously unknown to the civilized world. This island has a shape of perfect circle and it is inhabited by two tribes, Java and Seeplusplus. After a brief contact with the aborigines, Andrew found out that the boundary between the lands of the tribes is a straight line. Moreover, he knows the locations of several Java villages and of several Seeplusplus villages (each is of course located within or on the boundary of the corresponding tribe's land). Now he needs to find out what is the minimal and maximal possible area of Java's land. Help him!

Входные данные

The first line of the input file contains one integer r — the radius of the island (1 ≤ r ≤ 10^9). The next line contains one integer n (1 ≤ n ≤ 50000) — the number of Java villages. Each of the next n lines contains two integers x and y — the coordinates of Java villages. The next line contains one integer m (1 ≤ m ≤ 50000) — the number of Seeplusplus villages. Each of the next m lines contains two integers x and y — the coordinates of Seeplusplus villages. The center of the island has coordinates (0, 0), each village is within the island and at least r/10 away from the island boundary. No two villages coincide. The input is guaranteed to be valid — there will always be at least one straight line separating the Java villages from the Seeplusplus villages.

Выходные данные

Output two floating-point numbers, separated with a space — the minimal and maximal possible area of the Java land. An area will be considered correct if it is within 10^{-6} relative error of the right answer.

Пример

Входные данные #1
6
2
3 4
-3 4
1
0 0
Выходные данные #1
12.389928320447162 56.54866776461629
Автор Пётр Митричев
Источник Зимняя школа, Харьков 2011, День 8