아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

점

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

요약
흰 점을 꼭짓점으로 하고 내부에 검은 점이 없는 삼각형 개수를 셉니다.
난이도

보통10점 중 7점

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

문제

평면 위에 n+mn + m개의 점이 있습니다. 이 중 정확히 nn개는 흰 점이고, 나머지 mm개는 검은 점입니다.

흰 점 세 개를 꼭짓점으로 하는 삼각형 중에서, 내부에 검은 점을 하나도 포함하지 않는 삼각형의 개수를 구하세요.

어떤 세 점도 한 직선 위에 있지 않다고 가정할 수 있습니다.

입력

첫째 줄에 두 정수 nn과 mm (0≤n,m≤5000 \le n, m \le 500)이 주어집니다. 각각 흰 점의 개수와 검은 점의 개수를 의미합니다.

이어지는 nn개의 줄에는 흰 점의 좌표가, 그다음 mm개의 줄에는 검은 점의 좌표가 주어집니다. 각 줄에는 두 정수 xx와 yy (−109≤x,y≤109-10^9 \le x, y \le 10^9)가 주어지며, 점의 좌표를 나타냅니다.

출력

흰 점을 꼭짓점으로 하며 내부에 검은 점을 하나도 포함하지 않는 삼각형의 개수를 한 줄에 출력합니다.

힌트

위 그림은 첫 번째 예제를 나타낸 것입니다.

예제3

  1. 예제 1

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

    입력
    3 1
    0 0
    10 0
    0 10
    1 1
    
    예상 출력
    0
    
  3. 예제 3

    입력
    3 1
    0 0
    10 0
    0 10
    100 100
    
    예상 출력
    1