I'm struggling to find the idea behind solving this problem Polygon Cutting, anyone can help?
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3821 |
3 | Benq | 3736 |
4 | Radewoosh | 3631 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3388 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 161 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
I'm struggling to find the idea behind solving this problem Polygon Cutting, anyone can help?
Name |
---|
Consider building a graph: there is a node representing each piece and the weight of that node is the area of the piece. An edge is added between two nodes whose corresponding pieces share an edge.
Claim: This graph is a tree.
Proof idea: Each line segment inside the polygon splits the remaining area into two disjoint parts, similar to how each edge in a tree splits it into two disjoint trees.
We can figure out the vertices of each piece and the edges of the tree with the help of a monotonic stack:
Let's go through the vertices of the polygon in clockwise order and for each vertex, let's go through line segments starting/ending there in counterclockwise order. We'll keep a stack of current pieces and add / remove them from the stack once we've completely considered them. With this we can figure out the vertices of each polygonal piece and the edges of the tree.
My explanation is not very clear, so hopefully this animation is helpful: https://i.imgur.com/AVYpK3J.gif (I don't know how to embed gifs properly)
Once we have the vertices of each polygonal piece, we can calculate their areas easily with the formula from CPH chapter 29.2 (page number 271, page 281 of the pdf).
The rest can be solved with standard tree dp where every node has two states: pick this node or don't pick this node. Transitions are simple.
I can provide code if needed.
ohhhhh got it thank you, I'll try to implement it myself <3.
I didn't know this algorithm for building the graph. It's beautiful!
I used another well-know algorithm for building the dual of a planar graph to solve this problem. There's a template in cp-algorithms for finding the faces of a planar graph and building the graph from them should be straight-forward.