網際網路程式設計全國大賽

賽前測試題目

PROBLEM 2 Robot

Program fileROBOT.EXE
Input fileROBOT.IN
Output fileROBOT.OUT
Execution time30 s
這一題是有關機器人走路的問題。考慮下圖中的道路，路長 20 、寬度 16 ，上面有數個障礙物， 機器人不可以通過，分別為 (6,4) 、 (10,7) 、 (10,10) 、 (13,14) 四個點。機器人為圓柱形， 若直徑為 D ，根據這個圖的特性，我們可以分為通道 A 到 E ，容許機器人的直徑分別為 4 、 5 、 3 、 5 、 2 ，所以，當 D 的長度大於 5 時，機器無法通過圖中這條路。

輸入檔中每筆測試資料，第一行有三個數字 L 、 W 、 N ，分別為路的長度、寬度和障礙物的個數。 第二行起有 N 行資料，每行有二個數字 X 和 Y ，表示障礙點的位置，其中 X 為路左邊入口到點 的距離， Y 為上面的路邊到點的距離。第 N+2 行起會有數行測試資料，每行有一個數字 D ，表示 機器人的直徑，讀到 D 等於 0 為止。接下來是下一組測試資料，直到 L = W = N = 0 表示檔案結束。 若機器人可以從左邊走到右邊，請在輸出檔印 YES ，否則印 NO (都是大寫字母)，每一組的答案請輸 出在同一行中，列印 YES/NO 時多印一個空白分隔。這些數字都是不大於 1000 的整數，並且 0<=X<=L、0<=Y<=W。

範例﹕

ROBOT.IN
 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
ROBOT.OUT
YES NO
YES NO

提示﹕

這一題可以換個角度去做。把直徑為 D 的機器人看成一個點，障礙點看成直徑為 D 的圓， 路的兩邊向裡面各移入 D/2 。因此，題目就變成點是否可以通過一些圓形的障礙物。 判斷機器人能否通過，必須計算是否有一些障礙物聯集後，從路的一邊到另一邊形成一道垂直的牆。

你的程式，可以對每筆測試資料重新計算，但是，我們建議你直接算出機器人容許通過的寬度， 才會有最好的執行效率。

以下是範例中，根據 D=6 轉換的圖形。

接下來是 D=3 的圖形。

計算過程中，很可能會使用到浮點數，但在 N 很大時，會使程式變慢，所以最好避免大量使用。

下面是範例中第二個測試資料的參考圖形﹕

這條路，機器人最大直徑為 2.2361 。

註﹕障礙點可能重複。