PKU1092 - Farmland

This problem is from Korea Taejon regional 2001.

The general idea to this question is about:

Given a graph , you are asked to count how many polygons that satisfy the following properties:

1. It is a sided polygon
2. The area is positive
3. The polygon should not contains any vertex and edge inside (except the boundaries)

The idea is to enumerate all edges and to traverse if there exists a complete polygon-cycle.
The way to traverse is shown below:

1. Suppose we have a vector as a first to-be-traversed vector
2. 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
     
   • 
     
3. Then maximize
4. Replace by
   
5. 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.
6. If we have maintained a traversal list, check if the content is 2-repeated e.g. ABCDABCD
7. If is 2-repeated, has required length and anticlockwise in representation, we can conclude that it is a valid polygon that satisfies the constraints

Suppose we found a polygon-cycle ABCD, we know that there exists 4 different valid permutations, namely ABCD, BCDA, CDAB and DABC. It can be proved by the cycle properties possessed of the polygon-chain. Then, we can conclude that if we have found valid polygon-cycles, the actual answer would be since we can find all those permutations.

Struggled Testcase: