고대 탑

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

요약

N개의 점 중 네 점을 꼭짓점으로 삼아 넓이가 S 이상인 단순 사각형의 개수를 구합니다.

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

문제

네를로고니아의 왕은 평생 많은 땅을 정복했다. 이제 아들이 성년이 되어, 왕은 자신의 재산을 아들과 나누려 한다.

네를로고니아에는 평면 위의 점으로 볼 수 있는 고대 탑이 $N$ 개 있다. 왕은 아들이 이 중 탑 4개를 고르도록 정했다. 아들은 고른 탑을 꼭짓점으로 삼아, 탑끼리 벽으로 이어 사각형을 만든다. 사각형은 단순해야 하지만 볼록할 필요는 없다. 벽으로 둘러싸인 땅은 아들의 소유가 된다. 땅이 좁다고 놀림받지 않도록, 사각형의 넓이는 주어진 값 $S$ 이상이어야 한다.

아들은 땅을 고르고 싶어 하지만, 왕은 이것이 몇 가지 방법으로 가능한지 미리 알고 싶어 한다. 아래 그림은 $N = 4$ 인 경우의 예다. 이때 넓이가 $S = 2$ 이상인 서로 다른 사각형은 두 개다.

인접하지 않은 변끼리 교차하지 않는 사각형을 단순하다고 한다.

입력

첫째 줄에 두 정수 $S$ ( $1 \le S \le 10^{18}$ )와 $N$ ( $4 \le N \le 400$ )이 주어진다. 다음 $N$ 개 줄에는 각 탑의 좌표를 나타내는 두 정수 $X$ 와 $Y$ ( $0 \le X, Y \le 10^{9}$ )가 한 줄에 하나씩 주어진다. 같은 위치의 탑은 없으며, 세 탑이 한 직선 위에 놓이는 경우도 없다.

출력

탑을 꼭짓점으로 하고 넓이가 $S$ 이상인 서로 다른 단순 사각형의 개수를 한 정수로 출력한다. 꼭짓점이나 변이 하나라도 다르면 서로 다른 사각형으로 센다.

예제4

예제 1
입력
```
2 4
1 2
3 4
3 3
4 1
```
예상 출력
```
2
```
예제 2
입력
```
1 4
1 2
3 4
3 3
4 1
```
예상 출력
```
3
```
예제 3
입력
```
4 5
1 1
3 3
3 0
0 1
1 0
```
예상 출력
```
3
```
예제 4
입력
```
1 4
0 0
1000 0
0 1000
1000 1000
```
예상 출력
```
1
```