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
- 台灣網際網路程式設計全國大賽·賽前測試題目