시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB707715.909%

문제

다솜이는 엄청나게 큰 종이를 가지고 있다. 다솜이는 종이를 XY좌표로 생각한다. 그리고, 그 종이에 선을 N개 그었다. 선을 N개를 그리고 나서 종이를 본 후에 다솜이는 지금 내부에 선분이 없는 볼록 다각형이 총 몇 개가 있는지 궁금해졌다.

다솜이가 그은 선의 시작점과 끝점의 좌표가 주어졌을 때, 다각형이 총 몇 개 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 선의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 선분의 정보가 시작점의 X, Y좌표, 끝점의 X, Y좌표가 순서대로 주어진다. 모든 좌표는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이다. 모든 선분은 중복되지 않는다. 또, 시작점과 끝점이 같은 경우는 없다.

출력

첫째 줄에 다각형의 개수를 출력한다.

예제 입력 1

3
0 0 1 1
1 1 2 -1
2 -1 0 0

예제 출력 1

1

예제 입력 2

1
0 0 1 1

예제 출력 2

0

예제 입력 3

7
-10000 -9999 -10000 9999
-9999 10000 9999 10000
10000 9999 10000 -9999
-9999 -10000 9999 -10000
0 0 0 1
500 0 500 -1
-500 0 -500 -2

예제 출력 3

4

예제 입력 4

9
0 0 1 1
0 0 1 2
0 0 1 3
0 0 1 4
0 0 1 5
0 0 1 6
0 0 1 7
0 0 1 8
0 0 1 9

예제 출력 4

0

예제 입력 5

7
-1 -1 1 1
-1 -2 1 0
-1 0 1 2
-1 0 -1 -10000
1 10000 1 0
3 1 -3 -2
-3 -5 3 4

예제 출력 5

7

예제 입력 6

5
-100 -100 100 99
-100 -99 100 100
-100 -98 100 101
-100 -97 100 102
-100 -96 100 103

예제 출력 6

0

예제 입력 7

6
-100 -100 100 99
-100 -99 100 100
-100 -98 100 101
-100 -97 100 102
-100 -96 100 103
1 -1 -2 2

예제 출력 7

0

출처