Escape the Canyon

The prisoners are trying to escape from prison and reach a nearby village. However, between the prison (point A) and the village (point B) lies a canyon guarded by soldiers. Each soldier is stationed at a fixed position in the canyon and has a viewing range of \(100\) meters. The prisoners can only pass safely if at every point along their path their distance to the nearest soldier is more than \(100\) meters.

The canyon is modeled as a rectangle with a given length \(L\) and width \(W\) (the \(x\)-axis ranges from \(0\) to \(L\) and the \(y\)-axis from \(0\) to \(W\)). We assume that the prison is located at the west boundary (\(x=0\)) and the village at the east boundary (\(x=L\)). It is known from geometry that a safe passage from the prison to the village exists if and only if the union of the soldiers' observation circles (each a circle of radius \(100\)) does not form a continuous barrier cutting the canyon from its south boundary (\(y=0\)) to its north boundary (\(y=W\)).

You are given the dimensions of the canyon and the coordinates of each soldier inside the canyon. If the prisoners can cross safely without being seen (i.e. there exists a path from the west to east boundary that never comes within \(100\) meters of any soldier), output 0. Otherwise, determine the minimum number of soldiers that have to be eliminated (it does not matter if a soldier is seen by another soldier, he can still be eliminated) so that a safe path exists.

Notes on the model:

• Each soldier’s observation zone is a circle of radius \(100\). Two soldiers are considered connected if their circles intersect or touch, i.e. the Euclidean distance between their positions is at most \(200\).
• A soldier is connected to the south boundary if \(y - 100 \le 0\), and to the north boundary if \(y + 100 \ge W\). A continuous chain of soldiers connecting the south and north boundaries forms a barrier blocking any safe crossing.
• The minimum number of soldiers to eliminate is equivalent to the minimum vertex cut in the "obstacle graph" (where each vertex is a soldier and an edge exists between any two soldiers whose circles overlap) that disconnects the south boundary from the north boundary.

Hint: This problem can be solved by modeling it as a network flow problem. To handle vertex removals, split each soldier into two nodes with an edge of capacity \(1\) (the cost to remove that soldier). Connect two soldiers by an edge with infinite capacity if their observation circles intersect. Also, create a source that connects (with infinite capacity) to every soldier whose circle touches the south boundary, and a sink that every soldier whose circle touches the north boundary connects to (with infinite capacity). The answer is the value of the minimum cut (i.e. maximum flow) between the source and sink. If no path exists between the source and sink, no soldier removal is needed (output 0).

inputFormat

Input begins with three numbers \(L\), \(W\) and \(n\) (\(1 \le L, W \le 10^4\), \(0 \le n \le 500\)), representing the length and width of the canyon and the number of soldiers, respectively.

Then follow \(n\) lines, each containing two numbers \(x\) and \(y\) (\(0 \le x \le L,\ 0 \le y \le W\)), which denote the coordinates of a soldier.

outputFormat

Output a single integer, which is the minimum number of soldiers that need to be eliminated so that the prisoners can safely cross the canyon. If the prisoners can already cross safely without elimination, output 0.

sample

500 300 0

0