CarrotField
TCO 2014 Semifinal 1 · 2014-03-26 · by Errichto
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
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.
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...
20 22 25 Returns: 481.5403826061094
5 50 8 Returns: 85.87765067992017
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.
2386 12347 1234 Returns: 3571366.775318483
100 100 1 Returns: 3.141592653589793
example 0 before change to "100 100 1"
Submissions are judged against all 46 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CarrotField with a public method double expectedValue(int H, int W, int R) · 46 test cases · 2 s / 256 MB per case