직선

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

요약

평면 위의 N개 직선이 있고 일부는 겹칠 수 있다. 이 직선들이 평면을 나누는 영역의 수를 구한다. 서로 다른 교점의 개수를 세어 오일러 공식을 적용한다.

난이도: 보통10점 중 7점
유형: 기하, 수학, 해시맵, 구현
정답자: 아직 제출이 없습니다

문제

평면 위의 $N$ 개의 직선 $\ell_1, \ell_2, \ldots, \ell_N$ 이 입력으로 주어진다. 이 직선들이 평면을 나눌 때 생기는 영역의 개수를 구하는 프로그램을 작성하시오. 직선들 중에는 서로 겹치는 것이 있을 수도 있다.

아래 그림에서는 평면이 14개의 영역으로 나뉘어 있다.

입력

입력은 $N + 1$ 개의 줄로 이루어진다. 첫째 줄에 $N$ ( $1 \le N \le 1000$ )이 주어진다. $i + 1$ 번째 줄 ( $1 \le i \le N$ )에는 네 정수 $a_i, b_i, c_i, d_i$ ( $0 \le a_i, b_i, c_i, d_i \le 1000$ , $(a_i, b_i) \ne (c_i, d_i)$ )가 공백으로 구분되어 주어진다. 이는 직선 $\ell_i$ 가 두 점 $P_i(a_i, b_i)$ 와 $Q_i(c_i, d_i)$ 를 지나는 직선임을 뜻한다.

출력

표준 출력에 영역의 개수를 한 줄로 출력한다.

힌트

예제1

예제 1
입력
```
4
0 4 6 4
0 0 6 6
1 0 1 6
0 6 6 0
```
예상 출력
```
11
```