Nearest Points

Time limit2sMemory limit512 MB

Summary

Count the integer lattice points in an axis-aligned rectangle whose Euclidean distance to p1 is the minimum among K marked points.

Level: Hard9 of 10
Topics: Geometry, Divide and conquer, Sorting, Combinatorics
Solved: No attempts yet

Problem

On the Cartesian plane, let $A$ be a rectangle with sides parallel to the axes and vertices at $(0, 0)$ and $(X, Y)$ , where $X$ and $Y$ are positive integers. Inside this rectangle (including the boundary) there are $K$ points $p_1, p_2, \ldots, p_K$ with integer coordinates. A point $p$ in $A$ with integer coordinates is called good if the distance from $p$ to $p_1$ is no greater than the distance from $p$ to any of the points $p_i$ , $1 \leq i \leq K$ .

How many good points are there?

Input

The first line contains three positive integers $X$ , $Y$ , $K$ , $1 \leq X, Y, K \leq 2 \cdot 10^5$ : the dimensions of the rectangle and the number of marked points. The $i$ -th of the following $K$ lines ( $i = 1, 2, \ldots, K$ ) contains two integers $x_i$ , $y_i$ ( $0 \leq x_i \leq X$ , $0 \leq y_i \leq Y$ ): the coordinates of the $i$ -th point. All points are distinct.

Output

Print a single nonnegative integer: the answer.

Examples2

Example 1
Input
```
4 4 5
2 2
1 1
1 3
3 3
3 1
```
Expected output
```
5
```
Example 2
Input
```
6 6 6
0 0
1 0
2 0
3 0
4 0
5 0
```
Expected output
```
7
```