Baltic Olympiad in Informatics: 2007 Day 1, Problem 1

A group of war prisoners are trying to escape from a prison. They have thoroughly planned the escape from the prison itself, and after that they hope to find shelter in a nearby village. However, the village (marked as $B$, see picture below) and the prison (marked as $A$) are separated by a canyon which is also guarded by soldiers. These soldiers sit in their pickets and rarely walk; the range of view of each soldier is limited to exactly $100$ meters. Thus, depending on the locations of soldiers, it may be possible to pass the canyon safely, keeping the distance to the closest soldier strictly larger than $100$ meters at any moment.

You are to write a program which, given the width and the length of the canyon and the coordinates of every soldier in the canyon, and assuming that soldiers do not change their locations, first determines whether prisoners can pass the canyon unnoticed. If this is impossible then the prisoners (having seen enough violence) would like to know the minimum number of soldiers that have to be eliminated in order to pass the canyon safely. A soldier may be eliminated regardless of whether he is visible to any other soldier or not.

Constraints

$1\le W\le 50\cdot {10}^3$

$1\le L\le 50\cdot {10}^3$

$1\le N\le 250$

Input Specification

The first line contains three integers $L$, $W$, and $N$ - the length and width of the canyon, and the number of soldiers, respectively. Each of the following $N$ lines contains a pair of integers $X_i$ and $Y_i$ - the coordinates of $i$-th soldier in the canyon $(0\le X_i\le L,0\le Y_i\le W)$. The coordinates are given in meters, relative to the canyon: the southwestern corner of the canyon has coordinates $(0,0)$, and the northeastern corner of the canyon has coordinates $(L,W)$, as seen in the picture above.

Note that passing the canyon may start at coordinate $(0,y_s)$ for any $0\le y_s\le W$ and end at coordinate $(L,y_e)$ for any $0\le y_e\le W$. Neither $y_s$ nor $y_e$ need to be integer.

Output Specification

In the first and only line of output, the program should print the minimum number of soldiers that have to be eliminated in order for the prisoners to pass the canyon safely. If the prisoners can escape without any elimination, the program should print $0$ (zero).

Sample Input

130 340 5
10 50
130 130
70 170
0 180
60 260

Sample Output

1

Grading

Your program will receive partial credits if it can only determine whether the prisoners need to eliminate any guard at all in order to escape. For this, several test runs will be grouped to one test group. You will receive $30\mathrm{\%}$ of a test group's credits in case you determine for each test run correctly whether any guards need to be eliminated ($0$ means no guards need to be eliminated, any positive integer means that any number of guards need to be eliminated). You will receive $100\mathrm{\%}$ of a test group's credits in case you determine for each test run correctly how many guards need to be eliminated for the prisoners' escape.