시간 제한메모리 제한제출정답맞은 사람정답 비율
1.5 초 1024 MB36111035.714%

문제

신촌 근처에 있는 어느 평화로운 숲에 다음 사진과 같이 격자점 당 나무가 하나씩 심어져있다. 운영진들은 이 숲이 마음에 들었기에 여기서 사람들을 모아서 ICPC Sinchon Camp를 진행하려고 했다.

이렇게 해서 2021년 8월 21일 ICPC Sinchon Camp Contest를 숲에서 깨끗한 공기를 마시면서 진행하게 되었다. 이렇게 평화롭게 대회가 잘 진행되려고 하는 중에, 갑작스럽게 정체불명의 조직으로부터 이 숲을 공격 받기 시작했다. 신촌 숲에 서로 다른 위치 $N$개에 미사일이 날라오고 있다. ICPC Sinchon 운영진들은 미사일의 피해를 최소화하기 위해서 $M$개의 보호막을 곳곳에 있는 나무에 설치했다.

보호막이 설치된 나무들은 무사했지만, 미사일 간의 상호작용으로 인해서 그림과 같이 보호막이 설치되지 않은 몇몇 나무들이 불에 타고 있었다. 보호막이 설치되지 않은 나무의 좌표를 $(a,b)$라 하고 $i$번째 미사일이 떨어진 지점의 좌표를 $(x_i, y_i)$라고 할 때, 다음 조건을 만족하는 $c_1$, ..., $c_N$이 존재한다면 해당 나무는 불에 탄다.

  • $\displaystyle a=\sum_{i=1}^N c_i x_i$
  • $\displaystyle b=\sum_{i=1}^N c_i y_i$
  • $\displaystyle \sum_{i=1}^N c_i = 1$
  • $0 \le c_i \le 1$ ($1 \le i \le N$)

운영진들은 소방 헬기를 동원해서 빠르게 불을 끄고 사람들을 구하려고 한다. 다만 소방 헬기에 너무 많은 물을 담으면 이동 속도가 느려지기에 적당한 양의 물을 싣고 불을 끄려고 한다. 물의 적당한 양을 구하기 위해서는 불에 타고 있는 나무의 수를 정확하게 계산해야 한다. 미사일이 떨어진 지점의 좌표가 주어질 때, 불에 타고 있는 나무의 수를 구해보자.

입력

첫 번째 줄에 떨어지고 있는 미사일의 수 $N$과 설치된 보호막의 수 $M$이 주어진다. ($1 \le N, M \le 500\,000$)

두 번째 줄부터 $N$개의 줄에 걸쳐서 각 미사일이 떨어진 위치의 $x$좌표와 $y$좌표가 주어진다. 각 좌표값들은 $-10^9$ 이상 $10^9$ 이하의 정수이며 미사일이 떨어진 위치는 서로 다르다.

$N+2$ 번째 줄부터 $M$개의 줄에 걸쳐서 각 보호막이 설치된 위치의 $x$좌표와 $y$좌표가 주어진다. 각 좌표값들은 $-10^9$ 이상 $10^9$ 이하의 정수이며 보호막이 설치된 위치는 서로 다르다.

출력

불에 타고 있는 나무의 수를 출력한다.

예제 입력 1

5 5
3 1
1 4
4 3
4 5
6 3
3 1
1 2
5 3
1 4
3 4

예제 출력 1

10

출처

Camp > ICPC Sinchon Algorithm Camp > 2021 ICPC Sinchon Summer Algorithm Camp Contest - 중급 G번