문제
여러분은 평면상에 어떠한 세 점도 같은 직선 위에 있지 않도록 점을 N개 받았다.
주어진 점 두개를 이은 어떤 선분 S는 다음의 조건을 만족할 때 '깔끔하다' 라고 정의한다:
주어진 점 두개를 이은 S가 아닌 모든 선분에 대해, S와 교차하지 않는다.
서로 다른 점 A, B, C, D에 대해 선분 AB와 선분 CD가 양 끝점이 아닌 다른 점에서 만날 경우 두 선분을 교차한다고 정의한다.
모든 점 쌍을 이은 선분들 중, 깔끔한 선분의 개수를 구하시오.
<Subtask>
#1 (5점) : N<=40
#2 (6점) : N<=200
#3 (89점) : 제한 없음
입력
첫 줄에는 점의 개수를 나타내는 정수 N (3 ≤ N ≤ 1000)이 주어진다.
그 이후 N줄에 걸쳐 i번째 점의 좌표를 나타내는 두개의 정수 (Xi, Yi)가 주어진다. (-109≤ Xi, Yi ≤ 109)
출력
주어진 점 집합에 대해 깔끔한 선분의 개수를 출력한다.
예제1
입력
4
11
-11
-1-1
1-1
출력
4
예제2
입력
4
-1-1
1-1
01
00
출력
6
힌트
출처
coci 2020/2021 contest6