PROBLEM LINK:
Author: ???
Tester: Kevin Atienza, Jingbo Shang
Editorialist: Kevin Atienza
PREREQUISITES:
Computational geometry, intersection, convex polygons
PROBLEM:
Given n convex polygons, find the area of their intersection.
QUICK EXPLANATION:
The intersection of two convex polygons is convex. We can use divide and conquer:
- Split the list of polygons into two, and recursively take the intersection of both halves.
- Take the intersection of these intersections.
To compute the intersection of two convex polygons A and B:
- Collect all vertices of A contained in B.
- Collect all vertices of B contained in A.
- Collect all intersections of all sides of A and B.
- Sort these points in polar order relative to their average. The answer is the polygon obtained with these points as vertices.
To check whether a point p is in a convex polygon:
- For every two vertices v and w in clockwise order, compute the cross product (v-p) \times (w-p).
- If all products are the same sign, then output “yes”, otherwise output “no”.
To compute the area of a polygon, use the shoelace formula.
EXPLANATION:
Intersecting two general polygons is tricky, but with convex polygons, things are much easier. For instance, the intersection of two convex polygons is another convex polygon, whereas the intersection of two general polygons may be disjoint!
Since the intersection of two convex polygons is a convex polygon, we may simply intersect our list of n polygons two by two, until we end up with just one polygon, at which point we simply output its area. Thus, we are left with two subproblems:
- Find the intersection of two convex polygons
- Find the area of a polygon
Intersection of two convex polygons
Let’s now try to compute the intersection of two convex polygons. As with normal polygons, each vertex of the intersection is either a vertex of an input polygon contained in the other input polygon, or an intersection of sides of the input polygons. The usual problem is that there are too many intersections, so the challenge is how to compute the actual vertices quickly, and also what the order is. This gets much tougher because as said earlier, the intersection might consist of multiple disjoint polygons!
But since the polygons that we have are convex, things are much much much easier for us. The intersection of two convex polygons is a convex polygon, and since we already know the set of vertices of this convex polygon (by above), it follows that the intersection must be the convex hull of the set of its vertices. The convex hull is easy to compute! (Using, for example, Graham scan.)
But we don’t even have to use a convex hull algorithm in our case, because the vertices already form a convex polygon! We simply have to sort them in a given direction (clockwise or counterclockwise), with respect to a point inside it or on its boundary. (The sorting step of Graham scan is basically this.)
Thus we now have a simple algorithm to compute the intersection of two convex polygons! What is the time complexity? Suppose the polygons have a and b vertices, respectively. Then it takes O(ab) to compute the set of vertices, and O(ab \log ab) time to sort them, so the overall running time is O(ab \log ab). But this is a rather loose bound. For example, we can actually prove that the number of vertices in the intersection is at most 2\min(a,b), because each side can only intersect the other convex polygon at most twice. So the running time is actually O(ab + \min(a,b) \log\min(a,b)) = O(ab). This can be optimized to the optimal O(a+b) by using more sophisticated techniques, but these are needlessly complicated for our purposes, so we’ll just say the running time is O(ab) 
Area
Now that we have the intersection, it’s time to compute its area. For this task, the very standard shoelace formula works very well, and runs in linear time. It says that the area is the following:
where (x_1,y_1),\ldots,(x_m,y_m) are the coordinates of the vertices of the polygon, and (x_0,y_0) = (x_m,y_m).
This formula works for any polygon, not just convex ones, but this is particularly easy to visualize with convex polygons. Let’s assume that the polygon contains the origin. First, notice that \frac{1}{2}\left(x_{i-1}y_i - y_{i-1}x_i\right) is just the (signed) area of the triangle with vertices (0,0), (x_{i-1},y_{i-1}) and (x_i,y_i). Thus, the formula above simply sums a bunch of triangles, one for each side, and it can easily be seen that all m triangles comprise the whole area of the polygon! Furthermore, since we are traversing in just one direction around the polygon, all signed areas have the same sign, so no cancellation occurs. The final absolute value simply removes the sign.
For polygons not containing the origin and nonconvex polygons, the visualization is slightly more involved, because there is cancellation involved. But it’s still interesting to visualize it and see which parts of the signed areas cancel one another, and why in the end only the area of the polygon remains counted. We invite the reader to investigate it themselves.
Point in polygon
As a side note, we didn’t mention how to check whether a point is inside a polygon. This is the standard “point in polygon” problem, and is very simple to solve if the polygon is convex. To check whether a point p is in a convex polygon, simply perform the following:
- For every two vertices v and w in clockwise order, compute the cross product (v-p) \times (w-p).
- If all products are the same sign, then output “yes”, otherwise output “no”.
Note that this is intuitive after visualizing how the shoelace formula works for convex polygons.
Running time
The running time of our algorithm is dominated by the taking of intersections of the n polygons. Let’s investigate the overall running time.
- In the 1st step, we are intersecting polygons with at most c and c vertices, respectively. This runs in O(c^2).
- In the 2nd step, we are intersecting polygons with at most 2c and c vertices, respectively. This runs in O(2c^2).
- In the 3rd step, we are intersecting polygons with at most 3c and c vertices, respectively. This runs in O(3c^2).
- In the 4th step, we are intersecting polygons with at most 4c and c vertices, respectively. This runs in O(4c^2).
- …
By summing the running times, we get O(\frac{n(n+1)}{2}c^2) = O(n^2 c^2), which is definitely good enough to pass the time limit!
If your algorithm to intersect two polygons with a and b vertices instead runs in O(a+b) time, then the running time is O(n^2c). This can be optimized to just O((n \log n)c) by doing divide and conquer: Recursively take the intersection of the first and second halves of our polygons, then take the intersection of the two resulting polygons.
Another solution
Here we describe another solution. In this solution, instead of taking the intersections of convex polygons pair by pair, we simply compute the vertices of the overall intersection. This is possible because we know that the candidate vertices of the overall intersection is either a vertex of some input polygon, or the intersection of two sides of some input polygon, and such a candidate is an actual vertex if and only if it is contained in all input polygons. Thus, we now have the following procedure to find the intersection:
- Discover the candidate points (vertices of input polygons and intersection of sides of polygons)
- Filter out candidate points that are not inside all polygons.
- Sort the given points either clockwise or counterclockwise.
- Take the area.
We already know how to perform all but the first step. To do the first step, simply take all vertices of input polygons, and use a “line segment intersection” routine to get all intersections of all pairs of sides.
Now, what is the running time? Since every pair of polygons can have up to c candidate points, there are O(n^2c) candidate points all in all. Checking whether a point is contained in all polygons runs in O(nc). Thus, the overall running time is O(n^3 c^2). This is worse than our solution above, but still passes the time limit due to the rather loose bounds for n and c.
Time Complexity:
O(n^2 c^2)
AUTHOR’S AND TESTER’S SOLUTIONS:
[setter][333]
[tester][444]
[editorialist][555]
[333]: The link is provided by admins after the contest ends and the solutions are uploaded on the CodeChef Server.
[444]: The link is provided by admins after the contest ends and the solutions are uploaded on the CodeChef Server.
[555]: The link is provided by admins after the contest ends and the solutions are uploaded on the CodeChef Server.