삼각형 세기

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

요약

N개의 정수 좌표 점 중 세 개를 골라 만든 삼각형이 원점을 내부에 포함하는 경우의 수를 센다.

난이도: 어려움10점 중 8점
유형: 기하, 정렬, 투 포인터, 조합론
정답자: 아직 제출이 없습니다

문제

베시는 망루에서 보초를 서며 소 떼를 지켜보고 있다. 무료함을 달래기 위해 베시는 목초지를 $XY$ 평면이라고 생각하고 소들이 서 있는 위치를 살펴본다.

소는 모두 $N$ 마리( $1 \le N \le 100000$ )이며 $1$ 번부터 $N$ 번까지 번호가 매겨져 있다. $i$ 번 소는 정수 좌표 $(X_i, Y_i)$ 에 서 있으며 $-100000 \le X_i, Y_i \le 100000$ 을 만족한다. 원점 $(0, 0)$ 에 서 있는 소는 없고, 원점은 어떤 두 소를 잇는 선분 위에도 놓이지 않는다.

베시는 서로 다른 세 소를 꼭짓점으로 하는 모든 삼각형을 머릿속으로 만든다. 그런 삼각형이 원점을 내부에 완전히 포함하면 이를 황금 삼각형이라고 부른다.

모든 소의 위치가 주어질 때, 황금 삼각형이 몇 개인지 구하여라.

입력

첫째 줄에 정수 $N$ 이 주어진다.
다음 $N$ 개의 줄에는 각각 한 소의 좌표 $X_i$ 와 $Y_i$ 가 주어진다.

출력

세 소로 이루어진 삼각형 중 원점을 내부에 완전히 포함하는 것의 개수를 정수 하나로 출력한다.

예제7

예제 1
입력
```
5
-5 0
0 2
11 2
-11 -6
11 -5
```
예상 출력
```
5
```
예제 2
입력
```
1
1 1
```
예상 출력
```
0
```
예제 3
입력
```
2
3 4
-1 -1
```
예상 출력
```
0
```
예제 4
입력
```
3
0 5
-5 -3
5 -3
```
예상 출력
```
1
```
예제 5
입력
```
3
1 1
2 3
5 1
```
예상 출력
```
0
```
예제 6
입력
```
6
1 1
-2 3
5 2
-4 1
3 5
-1 2
```
예상 출력
```
0
```
예제 7
입력
```
6
3 1
1 3
-3 2
-2 -3
1 -3
4 -1
```
예상 출력
```
8
```