신호

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

요약

세 점이 한 직선 위에 있지 않고 네 점이 한 원 위에 있지 않은 n개의 점이 주어질 때, 모든 세 점 조합에 대해 그 세 점을 지나는 원 안이나 경계에 들어오는 점 개수의 평균을 구한다.

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

문제

어느 통신 회사가 베이징에서 GSM(이동전화) 통신망을 개발하고 있다. 이 통신망은 도시에 있는 $n$ 개의 집에서 사용할 수 있어야 하지만, 제한된 예산 때문에 회사는 안테나를 단 하나만 세울 수 있다.

안테나는 $n$ 개의 집 중 $3$ 개를 골라, 그 세 집을 지나는 원의 중심에 세운다. 그러면 이 원의 내부 또는 경계에 있는 모든 집이 안테나로부터 신호를 받을 수 있다. 회사는 세 집을 무작위로 고르려고 하며, 신호를 받을 수 있는 집의 수를 가늠하기 위해 가능한 모든 세 집의 선택에 대한, 신호를 받는 집 수의 평균을 구하고자 한다.

여러분이 할 일은 집들의 위치가 주어질 때 신호를 받을 수 있는 집 수의 평균을 구하는 것이다. 집의 위치는 평면 위의 정수 좌표로 주어진다. 어떤 세 집도 한 직선 위에 있지 않으며, 어떤 네 집도 하나의 원의 경계 위에 있지 않다.

입력

첫째 줄에 집의 수를 나타내는 양의 정수 $n$ ( $3 \le n \le 1500$ )이 주어진다. 이어지는 $n$ 개의 줄에 각 집의 위치가 주어진다. $1 \le i \le n$ 에 대하여, $i+1$ 번째 줄에 집 $i$ 의 좌표를 나타내는 두 정수 $x_i$ 와 $y_i$ 가 공백을 사이에 두고 주어진다.

모든 좌표는 정수이며 $-1000000 \le x_i, y_i \le 1000000$ 이다. 어떤 세 집도 한 직선 위에 있지 않으며, 어떤 네 집도 하나의 원의 경계 위에 있지 않다.

출력

신호를 받을 수 있는 집 수의 평균을 기약분수로 출력한다. 평균이 기약분수로 $\frac{p}{q}$ ( $q > 1$ )이면 p/q 형태로 출력하고, 평균이 정수이면 그 정수만 출력한다.

예제3

예제 1
입력
```
4
0 2
4 4
0 0
2 0
```
예상 출력
```
7/2
```
예제 2
입력
```
3
0 0
5 0
0 7
```
예상 출력
```
3
```
예제 3
입력
```
4
0 0
6 0
6 5
0 4
```
예상 출력
```
7/2
```