21589번 - 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 $x_1$, $y_1$, $x_2$ and $y_2$ (all between −2,000 and 2,000 inclusive), representing a line through points ($x_1$, $y_1$) and ($x_2$, $y_2$). 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.