Ostrich Passions#5774
Johnny recently had a mishap with the ostrich named Chuck. After managing to gather all the escaped ostriches, the farmer contemplated how to prevent such chaos in the future.
Johnny decided to construct new housing for the birds. He established watchtowers, each equipped with spotlights, and connected them using electrified barbed wire fences. This setup encloses a yard in the shape of a polygon with vertices, where the ostriches will reside. To facilitate easier monitoring, he plans to connect certain pairs of non-adjacent towers with partition walls, thereby dividing the yard into N-2 triangular sections, creating enclosures for the ostriches. Importantly, these walls must lie entirely within the polygon, and each enclosure must be a non-degenerate triangle, meaning it must have a non-zero area.
The farmer now needs to determine how to divide the yard. Help him analyze all possible wall arrangements. Johnny is interested in two questions — one simpler and one more complex. First, he wants to know which pairs of towers can have a wall between them in any division plan. Second, he wants to know the total number of possible division plans.
The first line of the input file contains the number (3 \leq N \leq 300) — the number of towers.
The following lines provide the descriptions of the towers in the order they are traversed. The -th line contains two integers x_i, y_i, each not exceeding 10^4 in absolute value — the coordinates of the -th tower.
It is guaranteed that the yard forms a polygon with a non-zero area that does not self-touch or self-intersect.
In the first line, output — the number of pairs of towers between which a wall can potentially be built.
Then, output pairs of tower numbers, one per line. The numbers in each pair should be in ascending order, and the pairs should be sorted first by the first number, then by the second number.
The last line should contain a single number — the number of ways to divide the yard into enclosures. Since this number can be quite large, output it modulo 2^{30} = 1073741824.
Example 1