#P6077. [BalticOI2007] Escape

[BalticOI2007] Escape

题目描述

战犯们企图逃离监狱,他们详细地计划了如何逃出监狱本身,逃出监狱之后他们希望在附近的一个村子里找到掩护。

村子(下图中的 B)和监狱(图中的 A)中间有一个峡谷,这个峡谷也是有士兵守卫的。守卫峡谷的士兵们坐在岗哨上很少走动,每个士兵的观察范围是 100100 米。士兵所处位置决定了战犯们能否安全通过峡谷,安全通过的条件就是在任何时刻战犯们距离最近的士兵大于 100100 米。

给定峡谷的长、宽和每个士兵在峡谷中的坐标,假定士兵的位置一直保持不变,请你写一个程序计算战犯们能否不被士兵发现,顺利通过峡谷。

如果不能,那么战犯们最少需要消灭几个士兵才能安全通过峡谷(无论士兵是否被另一个士兵看到,他都可以被消灭)。

输入格式

第一行有三个整数 llwwnn,分别表示峡谷的长度、宽度和士兵的人数。

接下来的 nn 行,每行两个整数 xix_iyiy_i,表示第 ii 个士兵在峡谷的坐标,坐标以米为单位,峡谷的西南角坐标为 (0,0)(0, 0),东北角坐标为 (l,w)(l, w),见上图。

注意:通过峡谷可以从 (0,ys)(0, ys),(其中 ysys 满足 0ysw0\leq ys \leq w) 到 (l,ye)(l, ye)(其中 yeye 满足 0yew0 \leq ye \leq w),其中 ysysyeye 不一定是整数。

输出格式

只有一行,为一个整数,即安全通过峡谷需要消灭的士兵的人数,如果不需要消灭任何士兵,则输出 00

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

提示

对于 100%100\% 的数据,满足:1w51041 \leq w \leq 5\cdot 10^41l51041\leq l \leq 5\cdot 10^41n2501\leq n \leq 2500xil0 \leq x_i \leq l0yiw0 \leq y_i \leq w