d905: 1. 機器人碰撞偵測
Tags :
Accepted rate : 25人/67人 ( 37% ) [非即時]
評分方式:
Tolerant

最近更新 : 2011-11-17 00:31

Content

X大購物中心設置了一個遊戲區,裡頭備有一塊N×N的正方形地墊(N為邊長),小朋友們可把他們喜愛的機器人放置於地墊上的任一位置中。機器人會直線前進,但不能轉彎,並且每一秒只能前進一格。前進方向有八種選擇(如下面圖一所示),一旦選定後就不能改變。圖二為一個範例:機器人在時間t = 0被置於座標(2, 1)的位置,前進方向為SE2秒過後(t = 2)機器人的座標為(4, 3)。當機器人走到地墊邊界時,就會停止前進。上述例子中機器人在t = 3之後都在座標(5, 4)的位置。

現在有一群小朋友帶著他們的機器人來到了遊戲區,各自把機器人放到地墊上,一開始機器人都在不同的位置,並且他們的前進方向可能都不一樣。請你寫一個程式來預測機器人是否會碰撞碰撞的定義為同一時間兩個或多個機器人在同一個位置。在上述例子中,若有另一機器人被擺至(2, 4)位置,其前進方向為E,則t = 3時兩個機器人將發生碰撞。再舉一例,在上述例子中若另一機器人被擺在(1, 4)位置,其前進方向為E,其碰撞時間為t = 4

當碰撞發生時,發生碰撞的機器人則停止前進。但尚未發生碰撞的機器人則會繼續行走。因此發生碰撞的時間及位置可能不只一組。

 

Input

第一行有一個正整數N (5 N ≤ 100)N代表地墊的邊長。

第二行有一個正整數M (2 M ≤ 10)M代表機器人的個數。

第三行開始,每行有四個正整數,第一個數字表示機器人的編號(編號從1開始),第二個數字表示機器人的起始位置(X, Y)座標中X的值,第三個數字表示機器人的起始位置(X, Y)座標中Y的值,第四個數字表示機器人的前進方向(以圖一括號內的數字表示,例如1代表N2代表NE3代表E……),每個數字中間皆以一個空白分開。

Output
如果將有碰撞情況發生輸出將發生碰撞的機器人編號(編號由小排到大列出),以及發生碰撞的最早時間(t = ?),同組碰撞情況只能有一組輸出。編號間請以一個空白分開,最後一個編號與時間請以一個逗號分開。若沒有碰撞情況,則輸出No collision!
Sample Input
輸入範例一
5
2
1 2 1 4
2 2 4 3


輸入範例二
5
3
1 1 1 5
2 2 2 3
3 5 3 6
Sample Output
輸出範例一
1 2,3


輸出範例二
No collision!
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (16%): 2.0s , <1K
公開 測資點#1 (16%): 2.0s , <1K
公開 測資點#2 (16%): 2.0s , <1K
公開 測資點#3 (16%): 2.0s , <1K
公開 測資點#4 (16%): 2.0s , <1K
公開 測資點#5 (20%): 2.0s , <1K
Hint :
  1. 碰撞的「位置」或「時間」不同時,視為不同組的碰撞。
  2. 當碰撞不只一組時,請先按時間順序,再按編號的字典順序輸出。
Tags:
出處:
99學年度北基區資訊學科能力競賽 [管理者:
pcshic (PCSHIC)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」