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.

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 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 |