시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
3.0 초 512 MB 264 13 (5%) 10
문제
$N$개의 점 $P_1, \cdots, P_N$이 주어진다. 이 중에서 세 점 $P_i, P_j, P_k (i < j < k)$를 선택하여 만들어지는 삼각형 중에서 넓이가 $A \over 2$ 이상, $B \over 2$ 이하인 것의 개수를 구하여라.
입력
첫 번째 줄에 세 정수 $N, A, B \; (3 \le N \le 2,000,\; 1 \le A \le B ≤ 4 \times 10^{12})$ 가 주어진다. 다음 $N$개의 줄의 $i$번째 줄에는 두 정수 $x_i, y_i (-10^6 \le x_i, y_i \le 10^6)$가 공백으로 구분되어 주어진다. 이는 $P_i$의 좌표가 $(x_i, y_i)$임을 나타낸다. 좌표가 같은 점들이 여러 번 주어지지 않는다. $3 \le N \le 800$인 입력에 대해 문제를 해결하면 10점을 얻을 수 있다.
출력
주어진 점 중 세 개의 점으로 이루어진 삼각형 중에서 넓이가 $A \over 2$ 이상, $B \over 2$ 이하인 것의 개수를 출력한다.
힌트
#### 예제 입력 1 ``` 4 2 3 0 0 0 1 1 2 2 0 ``` #### 예제 출력 1 ``` 2 ``` #### 설명 총 4개의 삼각형이 만들어지며, 각각의 넓이는 $\frac{1}{2} \;, \frac{2}{2} \;, \frac{3}{2} \;, \frac{4}{2} \;$이다. 이 중에서 $\frac{2}{2} \;$이상 $\frac{3}{2} \;$이하인 것은 두 개이다.
#### 예제 입력 2 ``` 4 1 1 0 0 0 1 1 1 1 0 ``` #### 예제 출력 2 ``` 4 ``` #### 설명 총 4개의 삼각형이 만들어지며, 모두 넓이가 $\frac{1}{2} \;$이다. 그러므로 4를 출력하면 된다.