만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

삼각형들

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

요약
N개의 점 가운데 세 점을 골라 만든 삼각형 중 넓이가 A/2 이상 B/2 이하인 것의 개수를 구합니다.
난이도

보통10점 중 7점

유형
정렬, 투 포인터, 기하
정답자
아직 제출이 없습니다

문제

NN개의 점 P1,…,PNP_1, \dots, P_N이 주어진다. 이 중에서 세 점 Pi,Pj,PkP_i, P_j, P_k (i<j<ki < j < k)를 골라 만든 삼각형 가운데 넓이가 A2\frac{A}{2} 이상 B2\frac{B}{2} 이하인 것의 개수를 구하여라.

입력

첫 번째 줄에 세 정수 NN, AA, BB (3≤N≤2 0003 \le N \le 2\,000, 1≤A≤B≤4×10121 \le A \le B \le 4 \times 10^{12})가 주어진다.

다음 NN개의 줄의 ii번째 줄에는 두 정수 xix_i, yiy_i (−106≤xi,yi≤106-10^6 \le x_i, y_i \le 10^6)가 공백으로 구분되어 주어진다. 이는 PiP_i의 좌표가 (xi,yi)(x_i, y_i)임을 나타낸다.

출력

주어진 점 중 세 점으로 이루어진 삼각형 가운데 넓이가 A2\frac{A}{2} 이상 B2\frac{B}{2} 이하인 것의 개수를 출력한다.

예제2

  1. 예제 1

    입력
    4 2 3
    0 0
    0 1
    1 2
    2 0
    
    예상 출력
    2
    
  2. 예제 2

    입력
    4 1 1
    0 0
    0 1
    1 1
    1 0
    
    예상 출력
    4