Problem1172--PIPI的高速公路

1172: PIPI的高速公路

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1078  Solved: 371
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI在某个地区修建高速公路,高速公路可以视为笛卡尔坐标系的X轴,长度为L。在一象限内有一些村庄,每个村庄的坐标用(x,y)表示,PIPI需要在高速公路上建造一些出口,任意村庄到高速公路的距离不超过D。请问,PIPI至少得建造多少个出口才能使得所有村庄到高速公路的距离不超过D???

Input

输入包含多组测试用例。
对于每组测试用例,第一行包含两个正整数 L 和 D,代表高速公路的长度和村庄离高速公路最大的距离D。(L<=20000,D<=50)
第二行包括一个正整数 n ,代表村庄的个数(n<=1000)。
接下来的n行,每行包括两个正整数 x y ,代表村庄的位置。

Output

对于每组测试用例,输出PIPI最少需要在高速公路上修建多少出口。

Sample Input

100 50
3
2 4
50 10
70 30

Sample Output

1

Source/Category