Hello everyone, today I’d like to ask a question related to computational geometry. I’d really appreciate your help. Thank you very, very much!
Problem summary:
You are given N convex polygons that are strictly nested — meaning some polygons are completely contained within others, forming a tree-like structure (polygon 1 is the outermost "root"). The polygons do not overlap, do not share edges, and each polygon either contains or is disjoint from others.
Each query gives a point (x, y). Your task is to find the polygon with the smallest area that contains this point.
Note: No point lies on the boundary of any polygon.
Input format:
The first line contains two integers: N and Q.
The next N lines describe the polygons. Each line starts with an integer k followed by 2k integers representing the k vertices in clockwise order: k x1 y1 x2 y2 ... xk yk
The last Q lines each contain a query point: x y
Input:
5 3
4 0 1 1 7 6 8 7 0
3 2 4 5 6 6 1
4 3 7 4 6 3 5 2 6
5 1 3 2 3 3 2 3 1 1 2
4 4 4 5 4 5 3 4 3
5 7
2 2
5 5
Output:
1
4
2
problem link: https://vjudge.net/problem/VNOJ-kingdoms
Auto comment: topic has been updated by bao987 (previous revision, new revision, compare).
For each stabbing line $$$x=a$$$, the order of points that intersect $$$x=a$$$ do not change for $$$x=a+\epsilon$$$, except for when a polygon is added to or removed around $$$x=a$$$. Therefore, you can maintain a balanced binary search tree of points that pass through $$$x=a$$$. This is possible because points already inside the set do not change their relative order regardless of a new polygon being added or removed.
Then, you get a sweepline algorithm by sweeping $$$x=a$$$ over $$$-\infty \lt a \lt \infty$$$. Based on how you process the stabbing line queries, you will get a $$$\mathcal{O}(n \log n)$$$ or $$$\mathcal{O}(n \log^2 n)$$$ algorithm. This should also work for any polygons that are $$$x$$$-monotone (that is, any $$$x=a$$$ will pass through any given polygon at most twice). For polygons that are not $$$x$$$-monotone, it should be slightly more complex as there are more than $$$2$$$ events processed per polygon.
For querying the deepest polygon which contains the point, the problem is equivalent to finding the deepest bracket pair that includes an index, given a dynamic array representing a bracket string. It is left as a practice for the reader to solve this using segment trees, and it is then straightforward to implement it using a BBST if you know how to use it.
The problem is solved in $$$\mathcal{O}(n \log n)$$$ or $$$\mathcal{O}(n \log^2 n)$$$ time.
Sorry, may I ask a bit more: do you mean that each event corresponds to a vertex sweep? And if we sweep by vertices, then each vertex will have two edges associated with it in one event. So how do we handle each of these events?
Apologies — I'm still not very good at these kinds of problems.
Ah, I understand how sweepline works now, but the problem is my code is running into TLE. So, is it really necessary to switch to a BBST? If not, how can I optimize it now (since I haven't learned BBST yet)? Link code: https://ide.usaco.guide/OVaceGEffjT2SpKEf-5
It should be more convenient for you to learn a BBST instead. That is, because we are inserting elements in the middle by some sorting condition instead of setting at some index, the usual segment tree "point-set" operation is almost unusable for this matter (or very inconvenient even if usable). Probably GNU PBDS (more informally known as ordered_set) may be fine for this matter alongside a custom sorting condition, but I have not tested it yet.
Thank you, but libraries like GNU PBDS are probably not allowed on OJ. If using a BBST, could you give me some suggestions? For example, how to insert, delete, and query?
I learned treaps (usually considered the most simple BBST) from cp-algorithms. Insertion and deletion are basic (as explained in the article). For queries, usually aggregates are stored in each node (by
x=op(op(left,self),right)), and you get the range aggregate of $$$[l,r]$$$ after splitting off $$$ \lt l$$$ and $$$ \gt r$$$ in $$$\mathcal{O}(\log n)$$$ time.Thank you