The general idea to this question is about:
Given a graph , you are asked to count how many polygons that satisfy the following properties:
- It is a sided polygon
- The area is positive
- The polygon should not contains any vertex and edge inside (except the boundaries)
The way to traverse is shown below:
- Suppose we have a vector as a first to-be-traversed vector
- Find a vector such that , and the anti-clockwise angle turned from to , is maximized. How to determine? We can try the following method:
- Let the inclined angle made by be .
- Let function
- Let a transformation is to rotate radian clockwise
- Then maximize
- Replace by
- Each time we log down how many times we have visited. If we have seen that is visited 3 times, then we can stop traversing.
- If we have maintained a traversal list, check if the content is 2-repeated e.g. ABCDABCD
- If is 2-repeated, has required length and anticlockwise in representation, we can conclude that it is a valid polygon that satisfies the constraints
Struggled Testcase:
沒有留言:
張貼留言