PROBLEM LINK:
Author: Praveen Dhinwa
Tester: Misha Chorniy
Editorialist: Animesh Fatehpuria
PROBLEM
There is an equilateral triangle ABC with side length 2 \cdot a. The coordinates of the triangle’s vertices are A = (-a, 0), B = (a, 0), C = (0, \sqrt{3} \cdot a). Next, there are three circles with centers at the midpoints of sides AB, BC and AC and radii r_1, r_2 and r_3 respectively. Compute the area of the intersection of the triangle and the three circles. The absolute or relative error should be atmost 0.05 and a \le 50.
EXPLANATION
First, we note that the desired accuracy for this problem isn’t as high as typical geometry problems. Additionally, a
is quite small as well. This suggests that we can use a monte-carlo or sampling based solution to approximate the answer with reasonable accuracy. Indeed, it turns out that this is one of the easiest ways to solve this problem.
Solution One: Breaking into Rectangles
The first solution (and probably the simplest) would be to partition the triangle into a bunch of really tiny rectangles
whose areas sum up to give a good enough approximation of the area of the triangle. We can then iterate over each such
tiny rectangle and check whether it lies within the three circles, and if so, add up that area. It turns out that using
0.01 \times 0.01 rectangles gives a good enough approximation for this problem.
To implement this, we can use the most brute force method possible. Since the area is bounded by 4400 units, we won’t
need more than 4400 \cdot 10^4 = 4.4 \times 10^7 rectangles. Further, checking if a rectangle is valid can be done in
O(1) since we just need to check if a point lies inside three circles. Thus overall, this method is fast enough.
Solution Two: Monte Carlo Based Simulation
Monte Carlo based solution Uniformly sample the points inside a triangle and check whether they belong to the three given circles. You need around 10^7 (or 5 * 10^6) samples to get the desired accuracy.
For checking how to uniformly sample the points in an equilateral triangle, see the http://mathworld.wolfram.com/TrianglePointPicking.html. The basic idea is as follows. Let OAB be the triangle where O is at the origin. Now, consider the vector OA and OB. Generate two numbers a, b in the range [0, 1] and the OC be the vector a * OA + b * OB. Note that point C is uniformly generated in the parallelogram made by OABD (where point D is such that BD is parallel to OA). If the point C doesn’t lie in the parallelogram, then we reflect it across the diagonal AB. This way, the point C will be a uniformly random point inside the triangle.
Another possible way could be sampling from a disk whose radius can be found as follows. Find the centroid D of the triangle. Find the radius R that is the distance between D and any of the vertices A, B, C. Now, randomly sample from a disc of radius R and check whether the point lies in each of the circles and the triangle. This method requires around 10^6 or more queries to get a good enough accuracy.
Solution three: Misha’s deterministic solution
There is a deterministic sweep line solution where you can move across the intersecting points and get the corresponding areas by using simple formulas.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.