P6077 [BalticOI 2007] Escape

War criminals are trying to escape from prison. They have carefully planned how to get out of the prison itself, and after leaving the prison they hope to find cover in a nearby village. Between the village (B in the figure below) and the prison (A in the figure) there is a canyon, and the canyon is also guarded by soldiers. The soldiers guarding the canyon sit on watchtowers and rarely move. Each soldier has an observation range of $100$ meters. The soldiers’ positions determine whether the war criminals can pass through the canyon safely. The condition for a safe passage is that at any moment, the distance from the war criminals to the nearest soldier is greater than $100$ meters. Given the length and width of the canyon and the coordinates of each soldier in the canyon, assuming the soldiers’ positions remain unchanged, write a program to determine whether the war criminals can pass through the canyon without being spotted. If they cannot, output the minimum number of soldiers that must be eliminated so that they can pass safely (a soldier can be eliminated regardless of whether they are seen by another soldier). 

The first line contains three integers $l$, $w$, and $n$, representing the length of the canyon, the width of the canyon, and the number of soldiers. The next $n$ lines each contain two integers $x_i$ and $y_i$, representing the coordinates of the $i$-th soldier in the canyon. Coordinates are in meters. The southwest corner of the canyon is $(0, 0)$ and the northeast corner is $(l, w)$, as shown in the figure above. Note: Passing through the canyon means going from $(0, ys)$ (where $ys$ satisfies $0 \leq ys \leq w$) to $(l, ye)$ (where $ye$ satisfies $0 \leq ye \leq w$). Here $ys$ and $ye$ do not have to be integers.

Output a single integer: the number of soldiers that must be eliminated to pass through the canyon safely. If no soldiers need to be eliminated, output $0$.

For $100\%$ of the testdata: $1 \leq w \leq 5\cdot 10^4$, $1 \leq l \leq 5\cdot 10^4$, $1 \leq n \leq 250$, $0 \leq x_i \leq l$, $0 \leq y_i \leq w$. Translated by ChatGPT 5