탈출해라, 다각형!

시간 제한2초메모리 제한512 MB

요약

정수 좌표로 주어진 최대 100000개의 꼭짓점을 가진 볼록 다각형에서 세 변의 직선이 삼각형을 이루고 그 안에 다각형이 들어가는 트리플의 개수를 셉니다.

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

문제

수상한 볼록 다각형 하나가 어떤 직선 방향으로 평행 이동해서 현재 위치를 벗어나려 한다. 아주 부지런한 직선 세 개가 다각형의 서로 다른 세 변을 따라 놓여 다각형을 가두려 한다. 세 직선이 삼각형을 이루고 다각형이 그 삼각형 안에 있으면 다각형은 갇히고, 그렇지 않으면 탈출한다.

위 그림 (a)는 다각형을 가두는 세 직선을 보여 준다. (b)에서는 두 직선이 평행해서 삼각형이 만들어지지 않으므로 다각형이 탈출한다. (c)에서는 다각형이 세 직선이 이루는 삼각형 밖에 있어서 쉽게 탈출한다.

다각형이 주어졌을 때, 다각형을 가둘 수 있는 서로 다른 세 직선의 조합의 수를 구하시오.

입력

첫째 줄에 다각형의 꼭짓점 수를 나타내는 정수 N (3 ≤ N ≤ 105)이 주어진다. 다음 N개 줄에 각 꼭짓점의 좌표를 나타내는 두 정수 X와 Y (−108 ≤ X, Y ≤ 108)가 주어진다. 꼭짓점은 반시계 방향으로 주어지며 단순 볼록 다각형을 이룬다. 세 꼭짓점이 한 직선 위에 있는 경우는 없다.

출력

주어진 다각형을 가둘 수 있는 서로 다른 세 직선의 조합의 수를 한 줄에 정수로 출력한다.

예제5

예제 1
입력
```
4
0 0
10 0
10 10
0 5
```
예상 출력
```
1
```

예제 2

입력

예상 출력

예제 3
입력
```
3
10 -10
0 10
-10 -10
```
예상 출력
```
1
```

예제 4

입력

6
-100000000 131
-50000067 -100000000
50000014 -100000000
100000000 -109
70000173 100000000
-90000011 100000000

예상 출력

예제 5
입력
```
4
0 0
10 0
10 10
0 10
```
예상 출력
```
0
```