PROBLEM LINK:Practice Setter: Alei Reyes DIFFICULTY:Hard PREREQUISITES:Centroid Decomposition, DisjointSets, Geometry and a knack of implementation. PROBLEM:Given an $N$ sided polygon on a 2Dimensional plane with points numbered from 1 to $N$ given in clockwise order, we are to process $Q$ queries.
QUICK EXPLANATION
EXPLANATIONThis problem is a complicated implementation (been saying that a lot lately, but what can I do? :P) First of all, Geometry Time Check if a point P lies on line segment joining A and B. Check if a point P lies inside triangle ABC if vertices are given in clockwise order. Area of triangle ABC, given coordinates of A(Ax, Ay), B(Bx, By) and C(Cx, Cy). About Triangles. For any polygon, we can represent it as the union of a number of nonoverlapping triangles by joining nonadjacent vertices of the polygon. See image for example The polygon with $N$ vertices is decomposed into $N2$ triangles. Also, all triangles do not overlap, thus the area of the polygon is just sum of areas of all these triangles. So, Beginning with our approach, let us reverse all queries. The problem looks like following. We now have a polygon having $N$ vertices with some fences added and we have to process two type of queries.
Though the problem looks still similar, we will see how it is beneficial to merge triangles rather than to split, by using Disjoint set Union, Each set initially consisting of one triangle initially, and another array storing areas of the triangles. When we remove a diagonal, Exactly two sets will merge, the regions, which were earlier divided by that diagonal. Areas also get merged. The real benefit of reversing queries is because it is far easier to get the area of the region, given area of subparts. Rather than finding the area of subregions formed due to new diagonal. Now, we have all small tools ready for solving this problem. By using all these tools, it is possible to solve this problem in $O(N*Q)$ by answering area queries in $O(N)$ by checking all triangles. If point lie inside any triangle, we can print area of the region which contains this triangle. Otherwise, if the query point lies on any fence, we need to check if this fence was removed. If yes, print area of the region. Otherwise, print 0. Now, $O(N*Q)$ is too slow to solve our problem, so we need an insight about Polygon Triangulation If we have a graph of $N2$ vertices each representing a triangle, and edge $(A, B)$ for all $A \neq B$ exist if triangle $A$ and triangle $B$ share an edge (not just corner), we get a tree. Also, consider the following image (Image credits to problem setter). The yellow region is connected to all regions while no other regions are connected with each other. Also, If we know, that query point say $J$ in the image, is lying to the left of segment DE, We can just ignore Blue and Green Regions, and move toward Red region. Now, we have a tree of regions. This gives us a different implementation to answer queries in $O(N)$ worst case. (will be helpful to reach our final solution.) For every query, just choose any triangle, check if query point lies inside that triangle. If yes, print area of the region containing that triangle. Otherwise, there will be one edge of this triangle, from which query point lies to the left side of the edge. Call this Special Diagonal Move toward triangle which shares special diagonal with current triangle. Continue this process until you reach the triangle which contains this triangle, or it is determined that point is outside the polygon. It is guaranteed that you'll visit all the triangles in the worst case. Also, make sure to check if a point lies on the border of any triangle. If that border is removed, print area of the region containing that border. Otherwise, print 0. This way too, we get $O(Q*N)$ time complexity, but this forms the base for optimizing this solution faster than a blink of an eye, just by Divide and Conquer Technique. Now, in this solution, once we move from one triangle to other, we never move back, thus reducing the size of search space by at least half the size of current search space, if we apply Divide and Conquer on trees, commonly known as Centroid Decomposition on tree, can read here. We still do the same thing, Choose a starting triangle, check if the point lies inside or on the border of this triangle. If no, we move toward component toward which has the next triangle. The thing about divide and conquer is, that we have almost the same idea, but just by choosing vertices carefully, we divide the search space into half at every step, resulting in $O(logN)$ steps. This complexity, combined with $O(logN)$ for usage of maps and other data structures, gives overall $O(Q*log^2 N)$ time complexity which is sufficient to fit the time limit. As for implementation, I have added linebyline comments in setter's solution which you may refer for implementation. Time ComplexityTime complexity is $O(Q*log^2 N)$. AUTHOR'S AND TESTER'S SOLUTIONS:Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)
This question is marked "community wiki".
asked 23 Oct '18, 23:30
