500. Circular Island

Time limit per test: 0.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard

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!
Input
The first line of the input file contains one integer r — the radius of the island (1 ≤ r ≤ 109). The next line contains one integer n () — 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 () — 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
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.
Example(s)
sample input
sample output
6
2
3 4
-3 4
1
0 0
12.389928320447176 56.548667764616276


Online Contester Team © 2002 - 2010. All rights reserved.