Problem E
Finding Polly
Where is Polly Polygon? She’s somewhere in the midst of a field of lines.
Given a set of lines, count how many non-self-intersecting polygons can be formed with exactly one segment from each line. Trivial segments (i.e., length 0) do not count. The polygon must contain exactly the same number of distinct vertices as there are lines in the field.
Input
The first line of input contains an integer $n$ ($3 \le n \le 12$), which is the number of lines in the plane.
Each of the next $n$ lines contains four integer coordinate values $x1$, $y1$, $x2$ and $y2$ (all between $-2\, 000$ and $2\, 000$ inclusive), representing a line through points $(x1,y1)$ and $(x2,y2)$. Note that they describe an infinite line, not just a line segment. All lines will be distinct. The two points defining a line will be distinct.
The input lines may be parallel. There may be points where more than two lines intersect. Intersections between lines may occur at points with coordinates greater than $2\, 000$.
Output
Output a single integer, which is the number of
non-self-intersecting polygons that can be formed with exactly
one segment from each line.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 0 0 0 1 0 0 1 0 0 2 1 0 2 0 0 1 |
2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
7 0 0 0 1 1 0 1 1 2 0 2 1 0 0 1 0 0 1 1 1 0 2 1 2 0 3 1 3 |
0 |
| Sample Input 3 | Sample Output 3 |
|---|---|
4 0 1 0 -1 1 0 -1 0 1 1 -1 -1 1 -1 -1 1 |
0 |
