500. Circular Island
Time limit per test: 0.25
Memory limit: 262144
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,
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
The next line contains one integer n
) — the number of Java villages. Each of the next n
lines contains two integers x
— 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
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.