만드는 중입니다

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

삼각형 안의 점

시간 제한1초메모리 제한512 MB

요약
주어진 N개의 점 가운데 세 점으로 만든 삼각형 중 내부에 점 P를 포함하는 삼각형의 개수를 구합니다. 변 위에 있는 경우는 제외합니다.
난이도

보통10점 중 6점

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

문제

좌표 평면에 NN개의 점이 주어진다. 이 중 3개의 점을 골라 만들 수 있는 삼각형 가운데, 점 PP를 내부에 완전히 포함하는 삼각형의 개수를 구하시오. 점 PP가 삼각형의 변 위에 놓인 경우는 세지 않는다.

입력

첫째 줄에 NN이 주어진다. 둘째 줄에 PP의 xx좌표와 yy좌표가 주어진다. 셋째 줄부터 NN개의 줄에 걸쳐 각 점의 xx좌표와 yy좌표가 주어진다.

출력

첫째 줄에 정답을 출력한다.

제한

  • 3≤N≤3×1053\leq N\leq 3\times 10^5
  • 모든 점의 좌푯값은 정수이며, 절댓값은 10910^9 이하이다.
  • PP를 포함한 모든 점의 좌표는 서로 다르다.

예제2

  1. 예제 1

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

    입력
    10
    4 -3
    -5 -10
    2 9
    4 -8
    9 -1
    -2 -7
    8 -7
    -6 1
    1 0
    -8 7
    -7 2
    
    예상 출력
    24