TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

92.9% (26/28)

Submission's AC Ratio

45.5% (35/77)

Tags

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 1

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 1

true
true
false

Hints

Problem Source

原TIOJ1462 / NPSC2007初賽(prob E)

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1