1410 - 机器人

Time Limit : 1 Second

Memory Limit : 128 MB

Submission: 54

Solved: 8

Description


这一题是有关机器人走路的问题。考虑下图中的道路,路长20 、宽度16 ,上面有数个障碍物,机器人不可以通过,分别为(6,4) 、(10,7) 、(10,10) 、(13,14) 四个点。机器人为圆柱形,若直径为D ,根据这个图的特性,我们可以分为通道A 到E ,容许机器人的直径分别为4 、5 、3 、5 、2 ,所以,当D 的长度大于5 时,机器无法通过图中这条路。




Input


输入文件中每组测试数据,第一行有三个数字L 、W 、N ,分别为路的长度、宽度和障碍物的个数。接下来N 行,每行有2个数字X 和Y ,表示障碍点的位置,其中X 为路左边入口到点的距离,Y 为上面的路边到点的距离。第N+2 行起会有若干行,每行有一个数字D ,表示机器人的直径,读到D 等于0 为止。一共有多组测试数据,直到L = W = N = 0 表示档案结束。


Output


若机器人可以从左边走到右边,请在输出档印YES ,否则印NO (都是大写字母),每一组的答案请输出在同一行中,打印YES/NO 时多印一个空白分隔(包括一行最后一个)。这些数字都是不大于1000 的整数,并且0<=X<=L、0<=Y<=W。


sample input
20 16 4
6 4
10 7
10 10
13 14
5
6
0
8 5 8 
2 1
1 3
3 2
4 4
5 3
6 4
7 2
7 1
2 
3
0
0 0 0
sample output
YES NO 
YES NO 
hint

这一题可以换个角度去做。把直径为D 的机器人看成一个点,障碍点看成直径为D 的圆,路的两边向里面各移入D/2 。因此,题目就变成点是否可以通过一些圆形的障碍物。判断机器人能否通过,必须计算是否有一些障碍物联集后,从路的一边到另一边形成一道垂直的墙。

你的程序,可以对每组测试数据重新计算,但是,我们建议你直接算出机器人容许通过的宽度,才会有最好的执行效率。

以下是范例中,根据D=6 转换的图形。

接下来是D=3 的图形。

计算过程中,很可能会使用到浮点数,但在N 很大时,会使程序变慢,所以最好避免大量使用。

下面是范例中第二个测试数据的参考图形﹕

这条路,机器人最大直径为2.2361

注﹕障碍点可能重复。

source
台灣網際網路程式設計全國大賽·賽前測試題目
© 2015 HUST ACMICPC TEAM. All Right Reserved.