PROBLEM LINK:
Author: Roman Furko
Tester: Kevin Atienza
Translators: Vasya Antoniuk (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Kevin Atienza
DIFFICULTY:
Hard
PREREQUISITES:
Green’s theorem
PROBLEM:
Given M circles and an N-vertex convex polygon, find the area of the parts of the polygon which are covered by some circle. In other words, find the area of the intersection of the polygon and the union of the circles.
QUICK EXPLANATION:
Let C be the union of the circles and P be the interior of the polygon. Then
\mathop{Area}(P) is easy to calculate, so let’s focus on \mathop{Area}(C) and \mathop{Area}(C \cup P). In both cases, we are dealing with the area of the union of circles and possibly a polygon.
Green’s theorem gives us a technique of finding the area based on the boundary of a region. Thus, we only need to compute the boundary of the union:
- For each circle, compute which parts of the circle are not contained in another circle/polygon.
- For each side of the polygon, compute which parts of the side are not contained in any circle.
Once we have all the parts of the boundary of the union, we can now calculate the area using Green’s theorem. (Note that we don’t have to know how these boundary parts are ordered around the boundary. We just need to add their individual contributions according to Green’s theorem.)
More details can be found in the explanation section. (Note: there are many other approaches as well)
EXPLANATION:
Disclaimer: This editorial focuses on just one possible solution. There may be (many?) other possible solutions. Also, I must admit that I skimmed over some details, so if you want to know these details, I suggest looking at my code (see editorialist’s solution below). Also, feel free to ask questions/clarifications.
Area relationships between union and intersection
To start with, let’s be clear about what the problem is. Let C be the union of all the circular areas, and let P be the polygonal area. What we’re looking for is \mathop{Area}(C \cap P). Computing this value seems a bit complicated because we are intersecting C and P, but C itself is a union of a bunch of other simpler regions (namely circles). It would be nice if we’re dealing with either pure unions or pure intersections, right?
That’s correct, and luckily there is a simple formula that we can use to get rid of the intersection, namely a relationship between \mathop{Area}(C \cap P) and \mathop{Area}(C \cup P). First, if C and P were disjoint, then \mathop{Area}(C \cup P) is simply the sum of the individual areas of C and P, or \mathop{Area}(C) + \mathop{Area}(P). However, if C and P are not disjoint, then \mathop{Area}(C \cup P) is not equal to \mathop{Area}(C) + \mathop{Area}(P), because some area is counted twice. Specifically, this area is the area common to both C and P, which is C \cap P by definition. Thus, we must adjust this formula so this area is counted only once. The corrected formula is
By rearranging this formula, we get
In the right hand side, \mathop{Area}(P) is easy to compute (it’s just the area of a polygon), so we’re left with the areas of C and C \cup P, both of which are pure unions of regions, so we have achieved what we wanted. Thus, all we need to do is solve the following problem:
Given a bunch of circles, and possibly one polygon, find the area of the union of all of them.
Computing \mathop{Area}(C) and \mathop{Area}(C \cup P) are both instances of this problem.
Area of union
We now want to compute the area of a bunch of circles (and possibly one polygon). What makes this complicated is that the said union of regions is very complicated: It can have many connected regions, holes, and a bunch of other complications. I mean, how are you going to find the area of a monstrosity such as the following?
Luckily, there’s a way of computing the area of a region, no matter how complicated, by performing an integral along the region’s boundary. This is with the help of Green’s theorem. To help you visualize, here’s an example of how to compute the area of a complicated blob using some integral around its boundary:
(This is also basically what makes the polygon area formula work.)
Here, O is the origin. Also, note that the areas involved in this sum are signed areas.
This technique even works even if there are multiple connected regions and even holes! The only thing to keep track of is the orientation of each boundary, because orientation is important when calculating signed areas.
Thus, in order to calculate the area of the above monstrosity, we only need to find the “pieces” of its boundary, and add up the contributions of each “piece” in the integral. The nice thing about this is that we don’t even need to know the “order” of these pieces along the boundary, because addition is commutative and associative! (This saves us the headache of having to handle separate connected components and “holes” in our figure.)
The following illustrates this strategy:
The boundary of the whole figure consists of pieces of circular arcs (from the circles) or straight segments (from the polygon). Now, all we need to do is to discover these “pieces” individually. Specifically:
- For each circle, determine which parts of its boundary are part of the boundary of the whole figure:
- For each side of the polygon, determine which parts of it are part of the boundary of the whole figure:
Once we figure these out, we only need to compute the contributions of these pieces to the integral. The contribution of a line segment piece is simple: it is simply a (signed) triangle area. The contributions of circular arc pieces are more complicated:
But luckily, each such contribution can be decomposed into three geometric figures, each of whose areas can be easily computed:
(Here, C is the center of the circle containing the arc.)
The first summand is a circular sector (whose area is simply a proportion of the area of the whole circle), and the other two are (signed) triangles (in which the area formula works).
This even works for arcs oriented “the other way”:
Or arcs oriented weirdly:
Or even arcs larger than a semicircle:
Thus, the remaining challenge is actually figuring out the “boundary pieces” themselves.
Boundary parts in a polygon side
Given a line segment (which is a side of our polygon), we want to know which parts of it are also part of the boundary of the whole figure. By definition, these are the parts which are not contained in any of the circles. Thus, all we need to do is remove the parts which are contained in some circle. In order to do this, we need to maintain a data structure on a line segment that supports the following operation:
- Given a subsegment of the line segment, remove it. (Note that some subsegments may be “removed” multiple times. In those cases, they must only actually be removed once.)
And then afterwards, the data structure must be able to give us a list of the remaining, unremoved subsegments of the original line segment.
For example, suppose we will operate on a line segment of length 100. Let’s mark the left and right endpoints as 0 and 100, respectively. Also, suppose that we want to remove the following subsegments: [10,50], [70,90] and [40,60]. Then the remaining subsegments will be [0,10], [60,70] and [90,100]. The following illustrates it:
Clearly, such a data structure will be useful because we will gradually remove parts of the line segment as we discover that some parts are contained in some circles. The implementation details will be explained in the appendix, but for now, let’s assume that we have such a structure.
Now, our goal is to gradually remove parts of the line segment that are contained in some circle. But with the data structure above, we can do this in a straightforward manner: We iterate over all circles, and for each circle, determine which part of the segment is contained inside the circle, and then remove this subsegment. To do so, however, we must be able to determine this contained segment in the first place. The following image illustrates the subsegment that we want:
Clearly, the endpoints of this subsegment are the intersections of the circle and the line segment. But this is a standard geometry problem and can be done in O(1) time! (See the appendix for details.) Thus, all we need to do is to compute these intersections.
A slight problem arises if the circle contains one of the endpoints of the original line segment, as in the following:
You need to handle these cases carefully.
Once we have removed the parts of the segment that are contained in other circles, we can now iterate over the remaining subsegments and add up the (signed) contributions of each subsegment in the total area!
Boundary parts in a circle
Given a circle, we want to know which parts of its boundary are also part of the boundary of the whole figure. This is similar to the previous problem, except this time instead of operating on a segment, we need to operate on a circular boundary, remove certain “sub-arcs” from this boundary, and then iterate on the unremoved “sub-arcs”. However, we can view a circle as a (curved) “segment” with length 2\pi r (where r is the radius), and so the “line segment structure” described in the previous section is still useful. (The difference from the previous problem is that the segment is now circular, so you’ll need to especially handle removals that “wrap around” the circle.)
Thus, we need to figure out which sub-arcs are contained in other circles, and the polygon. Figuring out which sub-arcs are contained in another circle is illustrated in the following:
The endpoints of this sub-arc are simply the intersections of the two circles. Finding these intersections is also a standard geometry problem. (The details are explained in the appendix.)
A special case occurs when the whole circle is contained in another circle. In this case, we simply ignore the circle altogether because we’re sure that none of its boundary is part of the boundary of the whole figure.
Now, what about finding which sub-arcs are contained in the polygon? This one is slightly more complicated, and is illustrated in the following:
The idea here is to iterate through the vertices of the polygon in some order, tracking every time we enter and exit the circle, and then removing the sub-arcs corresponding to the times when we are outside. This requires getting the intersection of a line segment and a circle, but we already have this operation. (We needed it before.)
Finally, once we have removed the parts of the circle that are contained in other circles or the polygon, we can now iterate over the remaining “sub-arcs” and add up the contributions of each sub-arc in the total area!
Wrap-up
There are quite a few small details and special cases skipped in this editorial, but I hope the general idea comes through: Find the boundary pieces of the whole figure, and then add up the contributions of these pieces to the integral. The idea sounds simple enough, but as usual with geometry problems, implementation is much harder than visualization (i.e., the devil is in the details). In case you think some details are missing, I encourage you to try filling them in on your own, because most of the little steps in this solution are actually bite-sized geometry subproblems that should each be (relatively) easy to solve on their own. This editorial simply explains how to put them all together (in general terms).
Finally, I mentioned this already but I will repeat it here: There may be other solutions to this problem. There might even be some solutions easier to implement or conceptually simpler than the one described here. If you find those solutions, then that’s nice, and I would be happy to hear about them.
Good luck!
Oh, and as for the time complexity, it depends on the efficiency of our “line segment structure”. The appendix explains one way of implementing it so that it can process Q operations in O(Q \log Q) time. Since there are O(N+M) operations each time we need such a structure, and (N+M) times we will need such a structure (one for each circle and polygon side), the overall complexity is O((N+M)^2 \log (N+M)).
Appendix 1: The “line segment structure”
Given a segment of length, say, L, we need to perform the following operation multiple times:
- Given a subsegment of the line segment, remove it (taking care that subsegments are only removed at most once).
After a bunch of removals, we will need to iterate over the list of “remaining subsegments”, i.e. subsegments that weren’t removed.
For simplicity, we will label the left and right endpoints of the segment as 0 and L. Also, assume that the i th removal is the removal of the segment [l_i,r_i] with 0 \le l_i \le r_i \le L.
Our solution will use the fact that we only have to make an offline version of this structure, meaning that we already know all removals up front and we just have to compute the unremoved subsegments. Since we already know the removals, we can chop our segment into subsegments whose endpoints are the endpoints of these removals. (If there are Q removals, then there are at most 2Q+2 endpoints.) This way, performing the removal [l_i,r_i] is simple: Simply remove the (chopped-up) subsegments that are completely contained in [l_i,r_i]! After processing all removals, only the unremoved segments will remain. This algorithm runs in O(Q^2) time.
Let’s use the example we used above: Suppose our segment has L = 100, and we will perform the following removals: [10,50], [70,90] and [40,60]. We illustrate it again here:
Then the chopped up subsegments are the following:
After processing the first removal [10,50], we will remove the subsegments [10,40] and [40,50] leaving:
After processing the second removal [70,90], we will remove the subsegment [70,90] leaving:
After processing the third removal [40,60], we will remove the subsegment [40,50] (which was already removed) and [50,60] leaving:
We are now left with the correct list of unremoved segments 
We can actually optimize this by structuring this list of chopped-up subsegments more efficiently. The idea is to insert them all in a self-balancing binary search tree. This way, when we process a new removal [l_i,r_i], we can quickly find the leftmost subsegment we need to remove. Overall, this takes O(Q \log Q) time.
Another way would be to process the removals a little differently and reduce it into an instance of offline range sum queries. If done correctly, this also takes O(Q \log Q) time.
Appendix 2: Intersection of a line segment and a circle
Here we will describe how to find the intersection of a line segment and a circle. The idea is to extend the line segment into a line, and then find the intersection of the line and the circle. Finally, only output the intersections that lie within the original line segment.
But we still need to find the intersection of a line and a circle. Suppose the line passes through the points P_1 and P_2, and the circle has center C and radius r. Then every point in the line is of the form P_1 + (P_2 - P_1)t for some real number t. (Here we’re thinking of the points as vectors.) Since we want to find such a point that is also on the circle, we need to find all t such that P_1 + (P_2 - P_1)t is r units away from C. In other words:
If you expand this equation, you’ll get a quadratic equation with t as the unknown, and such an equation can be solved by something as simple as the quadratic formula! This gives us (up to) two distinct values of t (which makes sense, because a line and a circle intersect in at most two points). Finally, note that P_1 + (P_2 - P_1)t lies within the line segment P_1P_2 if and only if 0 \le t \le 1, so we only need to consider t s satisfying this. Done!
Appendix 3: Intersection of two circles
Finally, we’ll need to find the intersection of two circles. Suppose the centers are C_1 and C_2 and radiuses are r_1 and r_2, respectively. This looks like a hard problem, so let’s try to simplify it.
For simplicity, let’s assume that C_1 \not= C_2, because otherwise, there would be no intersections. (unless r_1 = r_2, but then the circles are identical, so you should just remove identical circles from the input :P)
First, let’s translate the whole system by -C_1 so that the first circle is centered at the origin. We can just add C_1 to the intersection points after we’re done finding them. Thus, in what follows, we can assume that C_1 is the origin.
Next, let’s rotate the whole system about the origin so that C_2 is on the positive x-axis. We can just rotate back the intersection points we get after we’re done. Thus, in what follows, we can assume that C_2 = (x,0) for some x > 0. (And of course, C_1 = (0,0).)
At this point, the problem is actually simple enough for us to solve. Specifically, let’s say (X,Y) is an intersection point of both circles. Such a point must satisfy the equations of both circles, namely:
By simplifying this, we can actually compute X and Y as follows:
This gives us (up to) two intersections (X,Y)! (If r_1^2 - X^2 < 0, then we say that no intersection exists.)
Time Complexity:
O((N+M)^3) or O((N+M)^2 \log (N+M))