Vera has a yard in the shape of a rectangle with corners at and that is surrounded by a fence. She owns a cat who lives in a kitty house at and a rabbit who lives at . Her cat is evil and would eat the rabbit at night if given the chance. To protect her rabbit, Vera will install some lamps that will light up the yard at night. The cat is irrationally scared of lights and will not dare to enter any area that is lit by a lamp.
There are possible lamps that Vera can install. The -th lamp, if installed, will light an area in the shape of a circle with center and radius . Consider the cat as a point. The cat will be able to eat the rabbit if there exists a path from to that remains inside the yard and does not touch or intersect the area lit by any lamp.
It is acceptable to install a lamp that covers , in which case the cat will not be able to move anywhere as it cannot leave its kitty house.
There may be multiple possible lamps at the same point.
Vera does not want the lit area to be too big, so she would like to find a subset of the lamps to install such that her cat won't eat her rabbit and the total area lit by any lamp is minimum. This includes any area outside the yard that is lit by a lamp. Determine the minimum possible area of a valid installation of lamps.
It is possible that installing all the lamps will not stop the cat, in which case output 0.
Constraints
- All input are integers
Input Specification
Output Specification
Output one line with the minimum possible area.
If the cat cannot be stopped, output one line with 0.
Your answer will be considered correct if its absolute or relative error does not exceed .
Sample Input 1
3 6 3
2 3 3
3 0 2
4 2 1
Sample Output 1
14.7462241
Explanation of Sample Output 1
Vera can install the second and third lamps. Installing the first lamp is a less optimal solution as it has an area of .
Sample Input 2
2 3 4
0 2 1
3 2 1
Sample Output 2
0
Explanation of Sample Output 2
Installing both lamps will not stop the cat.
Comments