가장 가까운 점

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

요약

직사각형 안의 정수 격자점 가운데 p1까지의 거리가 K개 표시점 중 최소인 점의 개수를 센다.

난이도: 어려움10점 중 9점
유형: 기하, 분할 정복, 정렬, 조합론
정답자: 아직 제출이 없습니다

문제

좌표평면에 축에 평행한 변을 가진 직사각형 $A$ 가 있고, 두 꼭짓점은 $(0, 0)$ 과 $(X, Y)$ 이다. 여기서 $X, Y$ 는 양의 정수이다. 이 직사각형의 닫힌 내부에 정수 좌표를 가진 $K$ 개의 점 $p_1, p_2, \ldots, p_K$ 가 표시되어 있다. $A$ 에 속하면서 정수 좌표를 가진 점 $p$ 가, $p_1$ 까지의 거리가 모든 $p_i$ ( $1 \leq i \leq K$ )까지의 거리 이하이면 좋은 점이라고 한다.

좋은 점은 모두 몇 개인가?

입력

첫 줄에 세 양의 정수 $X$ , $Y$ , $K$ 가 주어진다. $1 \leq X, Y, K \leq 2 \cdot 10^5$ 이며, 직사각형의 크기와 표시된 점의 개수이다. 다음 $K$ 개 줄 중 $i$ 번째 줄 ( $i = 1, 2, \ldots, K$ )에는 두 정수 $x_i$ , $y_i$ 가 주어지며, $0 \leq x_i \leq X$ , $0 \leq y_i \leq Y$ 인 $i$ 번째 점의 좌표이다. 모든 점은 서로 다르다.

출력

정답을 나타내는 음이 아닌 정수 하나를 출력한다.

예제2

예제 1
입력
```
4 4 5
2 2
1 1
1 3
3 3
3 1
```
예상 출력
```
5
```
예제 2
입력
```
6 6 6
0 0
1 0
2 0
3 0
4 0
5 0
```
예상 출력
```
7
```