Criss-Cross

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

요약

최대 1000개의 선분 가운데 교차하거나 맞닿는 서로 다른 점의 개수를 구하며, 한 직선 위에서 겹치는 선분 쌍은 무시합니다.

난이도: 보통10점 중 5점
유형: 기하, 해시맵, 완전 탐색
정답자: 아직 제출이 없습니다

문제

피터는 운영체제 수업이 지루해서 종이에 낙서를 한다. 그는 자를 이용해 추상화를 그리고 싶어 한다. 평면 위의 두 점을 골라 선분으로 잇는 방식으로, 선분을 아주 많이 그린다.

그려진 선분들이 교차하거나 접하는 서로 다른 점의 개수를 세는 프로그램을 작성해 보자.

입력

첫째 줄에 선분의 개수 $n$ ( $1 \le n \le 1\,000$ )이 주어진다. 이어지는 $n$ 개의 줄에는 정수 네 개 $x_0$ , $y_0$ , $x_1$ , $y_1$ ( $-1\,000\,000 \le x_0, y_0, x_1, y_1 \le 1\,000\,000$ )이 차례로 주어진다. 선분의 길이는 0이 아니다. 즉 두 끝점은 서로 다르며, $x_0 \ne x_1$ 또는 $y_0 \ne y_1$ (또는 둘 다)이 성립한다.

출력

적어도 한 쌍의 선분이 그 점에서 교차하거나 접하는, 서로 다른 점의 개수를 출력한다.

두 번 이상 교차하거나 접하는 선분 쌍(즉 겹치는 선분)이 만들어 내는 교점은 세지 않는다.

두 선분이 끝점에서만 접하는 경우, 그 세 점은 한 직선 위에 있지 않다고 가정해도 된다.

예제3

예제 1
입력
```
3
1 3 9 5
2 2 6 8
4 8 9 3
```
예상 출력
```
3
```
예제 2
입력
```
3
5 2 7 10
7 4 4 10
2 4 10 8
```
예상 출력
```
1
```
예제 3
입력
```
3
2 1 6 5
2 5 5 4
5 1 7 7
```
예상 출력
```
1
```