PROBLEM LINK:
Authors: Triveni Mahatha
Tester: Jingbo Shang
Editorialist: Vaibhav Tulsyan
PROBLEM
You are given N semi-circles such that centres c(x_i, y_i) of the semi-circle lie on the X-axis and the semi-circle lies above the X-axis. Radius of the i^{th} semi-circle is r_i. Answer Q queries:
In each query, you are given a circle with centre C(X, Y) and radius R (y \ge R). Find the area within the circle that is overlapping with some part of any of the N semi-circles.
Constraints:
1 \le T \le 10
1 \le N \le 10^5
20 \le Q \le 200
1 \le r_i, R \le 10^5
1 \le x_i, y_i, X, Y \le 10^5
EXPLANATION
Note that the desired accuracy for this problem isn’t as high as typical geometry problems. Additionally, aa is quite small as well. This suggests that we can use a monte-carlo or sampling based solution.
Solution 1: Monte-Carlo Simulation
The high-level idea is as follows:
- Maintain a set of segments - the max y for each x. Note that the geometric figure is a semi-circle, whose equation can be treated as a function.
- For any x, we need to find the maximum value attained among all these N functions.
- This divides the X-axis into O(N) segments, such that for each segment, one of the given N functions attains max value.
- For each query circle, iterate over arcs and add area of intersection of query circle and arc to the total area.
How do we perform segmentation of X-axis?
This can be done in multiple ways.
- One of the way is to add discs one by one. Suppose at any point we know the partition (of X-axis) by first (i-1) discs. Now we want to add disc i. We can binary search for the center and find its probable position. Then we can remove zero or more discs in the vicinity of the new disc if the new disc dominates the entire segment of earlier dominated by a disc. Again, note that this is analogous to convex hull trick. This is O(N * log(N)).
- Another simpler way (implementation wise) is a divide and conquer method with same time complexity.
Divide the array at middle, find those segments for left and right, now merge them. How to merge? We will find the segments incrementally from smallest x co-ordinate to largest x. For simplicity in coding let’s say the smallest x is -\infty. Let’s denote the array of segments returned by recursion due to left half be S_1 and right half be S_2.
We keep a variable, last_X, which is initialized with -\infty. It denotes the x co-ordinate till which we have already merged. Now we find the leftmost segment from S_1 which is not covered till now. That is the one, denote a segment by seg(l, r, disc), where r > last_X. Call it s_1, and similarly find s_2 from S_2. Now we know that in the range (l, min(s_1.r, s_2.r)) one of s_1 or s_2 dominates (non other than them). We then find that out. After this step we know that we have considered everything till min(s_1.r, s_2.r). So we update the last_X accordingly. We repeat this till all the segments are covered from S_1 and S_2. Implementation wise till last_X is less than \infty.
Psuedo code:
vector<segment> solve(discs[1...n]) :
vector<segment> S1 = solve(discs[1..n/2])
vector<segment> S2 = solve(discs[n/2+1...n])
lastX = -inf
i1 = i2 = 0 // S1[i1] and S2[i2] are the current segments to be considered
vector<segment> ans; // to return
while lastX < inf :
while S1[i1].r <= lastX and i1 < len(S1) :
i1 += 1
while S2[i2].r <= lastX and i2 < len(S2) :
i2 += 1
update(ans, S1[i1], S2[i2], lastX, min(S1[i1].r, S2[i2].r))
lastX = min(S1[i1].r, S2[i2].r)
return ans
Generating points within query circle
We can throw x random points inside the query circle and check whether that lies inside some disc or outside. Now it’s just matter of estimating biasness of a coin with some confidence and some error margin. Here margin of error (E) is - 0.02.
If we throw x = 1.25 * 10^4 points, the confidence is 1 - 10^{-5}, which is quite high.
So, we need x * 200 checks overall. If we sort all these checks and then iterate, all the checks can be done in O(1) amortized time.
How do we uniformly choose points within the circle?
Reference: Wolfram
“To generate random points over the unit disk, it is incorrect to use two uniformly distributed variables r in [0, 1] and \theta in [0, 2 * \pi) and then take x = r cos(\theta), y = r sin(\theta), because the area element is given by dA = 2 * \pi * rdr, this gives a concentration of points in the center.”
Let a, b be two uniform distributions in [0, 1]. A random point (x, y) can be generated as follows:
x = R \sqrt{a} cos(2\pi b)
y = R \sqrt{a} sin(2\pi b)
Computing the common area between the circle and semi-circles
To check whether a point (x, y) is inside some disc, go to the disc which attains max value at x and check if the max value is less than y. This takes O(1) time apart from finding the right disc which takes log(N).
Solution 2: Deterministic Solution using Integration
- Using integration, every query can be answered in O(N).
- The solution involves computation of the integral of \sqrt{R^2 - x^2} across all segments.
- Eventually, we find area between each arc and the query circle.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.