TopCoder

Thumb output jddoia
$\huge 南ことり$
今天也要輸贏!?

User's AC Ratio

92.3% (12/13)

Submission's AC Ratio

35.4% (17/48)

Description

zun最近在玩一系列很有名的射擊遊戲,這個遊戲以華麗的彈幕和高難度的關卡吸引了不少玩家。網路上高手雲集,除了正規打法之外也發明了許多特殊的技巧,zun在看了這些奇奇怪怪的打法之後也想自己來開發新的打法。


由於人工控制的精密度有限,zun計畫要寫個程式偵測場上所有子彈的移動方式,自動規劃閃躲路線。對zun來說,要獨力完成這麼複雜的程式並不容易,所以他把程式切成好幾部分,分別請他認識的強者幫忙寫,完成其中一塊就是你的工作。

你的任務是:給定所有子彈的位置和方向,假設玩家從現在開始連續t秒停在某處不動,會不會被子彈擊中?

為了簡化問題,可以假設子彈以固定速度直線前進;子彈和玩家都是平面上的一個點,"打到"的定義是兩者在某時間有相同座標。

Input Format

輸入檔中有許多組測試資料。每組測試資料的第一行是四個整數n, t, p_x, p_y 分別表示場上的子彈數,玩家停止不動的時間(單位:秒),玩家的x和y座標。接著n行,每行四個整數x, y, v_x, v_y分別代表子彈的位置和移動的方向向量(e.g.: 子彈一秒後在(x+v_x, y+v_y), 兩秒後在(x + 2v_x, y + 2v_y),依此類推)。
保證n和t會大於0, 所有數字都是整數而且絕對值都不超過106
讀到n = t = p_x = p_y = 0時表示檔案結束,不須處理這組輸入。

Output Format

對每組測試資料輸出"true"或"false"(不含引號),表示玩家會不會被子彈擊中。

Sample Input

3 2 0 0
0 3 0 -2
-2 -1 1 0
2 -1 -1 0
4 2 0 0
0 2 0 -1
0 -2 0 1
2 0 -1 0
-2 0 1 0
4 1 0 0
0 2 0 -1
0 -2 0 1
2 0 -1 0
-2 0 1 0
0 0 0 0

Sample Output

true
true
false

Hints

Problem Source

原TIOJ1462 / NPSC2007初賽(prob E)

Subtasks

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB)
0 3000 65536