Hide

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

Please log in to submit a solution to this problem

Log in