Problem Statement

We have a rectangular field with corners in points (0,0), (0,H), (W, H), and (W, 0). There is a
carrot in every point with integer coordinates that lies inside or on the boundary of the field.
Thus, there are exactly (H+1)*(W+1) carrots.

Someone is going to drop a bomb onto this field. The point where the bomb lands will be chosen
uniformly at random from all points that lie inside or on the boundary of the field (including
points with non-integer coordinates). When the bomb lands, it explodes and destroys all carrots that
are within Euclidean distance R from the point of explosion.

You are given the ints H, W, and R. Return the expected number of destroyed carrots.

Method signature: double expectedValue(int H, int W, int R)
Time limit (s): 2.000
Memory limit (MB): 256

Notes

- Your return value must have absolute or relative error smaller than 1e-7.

Constraints

- H, W, and R will be between 1 and 100,000, inclusive.

Examples

0)

1
1
1
Returns: 3.141592653589793
The field is a 1x1 square with a carrot in each corner. Sometimes the bomb will destroy three of the
four carrots. Other times (when it drops somewhere around the center of the square) it will destroy
all four of them. Thus, the expected number of destroyed carrots must be somewhere between 3 and 4.
The exact value happens to be pi = 3.14159...


1)

20
22
25
Returns: 481.5403826061094


2)

5
50
8
Returns: 85.87765067992017


3)

100
100
999
Returns: 10201.0
Regardless of where the bomb drops, the radius of its explosion is so large that it will destroy all the carrots.


This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.