Finding Polly

시간 제한12초메모리 제한1024 MB

요약

n개의 직선 각각에서 정확히 한 선분씩 골라, 꼭짓점이 n개이고 자기교차가 없는 단순 다각형의 개수를 센다.

난이도: 보통10점 중 7점
유형: 기하, 백트래킹, 구현
정답자: 아직 제출이 없습니다

문제

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.

예제3

예제 1
입력
```
4
0 0 0 1
0 0 1 0
0 2 1 0
2 0 0 1
```
예상 출력
```
2
```

예제 2

입력

예상 출력

예제 3

입력

예상 출력