Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋君の秘書のなぎさちゃんは、高橋君が大好きです。今日も高橋君に電話をかけてみることにしました。 すると、どうでしょう? 電話口から、高橋君の声以外の、女の声が聞こえてきます。
なぎさちゃんは、高橋君と付き合ってはいませんが、高橋君に悪い虫が付いたら大変なので、浮気調査を行うことにしました。
高橋君の携帯に仕込んだアプリケーションから、高橋君の居場所をGPSで取得すると、高橋君は、電話をかける前は座標 (tx_a, ty_a) に、 電話をかけた後は、座標 (tx_b, ty_b) にいることがわかりました。また、この間にかかった時間は T 分です。 高橋君は、最大毎分 V の距離を移動することが可能であり、家などの障害物を無視して同じ速度で移動することが可能です。
なぎさちゃんは、このデータを元に、高橋君が、近所の女の子の家に寄っていないかを調査することにしました。 近所の女の子は n 人おり、それぞれ座標 (x_i, y_i) に住んでいます。
高橋君が、他の女の子の家に寄った可能性が少しでもある場合はYES
、そうでない場合はNO
と出力しなさい。
入力
入力は以下の形式で標準入力から与えられる。
tx_a ty_a tx_b ty_b T V n x_1 y_1 x_2 y_2 : x_n y_n
- 1 行目には、高橋君の電話前の座標を表す整数 tx_a, ty_a (0 ≦ tx_a, ty_a ≦ 1000)、電話後の座標を表す整数 tx_b, ty_b (0 ≦ tx_b, ty_b ≦ 1000)、移動に掛かった時間を表す整数 T (1 ≦ T ≦ 50)、高橋君の毎分の速度を表す整数 V (1 ≦ V ≦ 100)がスペース区切りで与えられる。
- 2 行目には、浮気調査の対象となる女の子の数 n (1 ≦ n ≦ 1000) が与えられる。
- 3 行目から n 行では、女の子の家の情報が与えられる。このうち i 行目では、i 番目の女の子の家の座標を表す整数 x_i, y_i (0 ≦ x_i, y_i ≦ 1000) が与えられる。
- 高橋君が、座標 (tx_a, ty_a) から、座標 (tx_b, ty_b)まで真っ直ぐ毎分 V 移動した時に、T 分より長くかかってしまうような入力は与えられない。
出力
高橋君が、他の女の子の家に寄ることが可能であればYES
、そうでなければNO
を 1 行で出力せよ。出力の末尾にも改行をいれること。
入力例1
1 1 8 2 2 4 1 4 5
出力例1
NO
高橋君が (1,1) から (8,2) に移動した際に、(4,5) の家に寄ることが可能かどうか考えます。
- (1,1)から(4,5)に移動する際、\sqrt{(4-1)^2 + (5-1)^2} = 5となるため、移動距離は 5
- (4,5)から(8,2)に移動する際、\sqrt{(8-4)^2 + (2-5)^2} = 5となるため、移動距離は 5
となり、総移動距離は10となります。
高橋君が移動可能な距離は、2 分間で 分速 4 なので、 8 までしか移動することが出来ません。
よって、高橋君がこの家に寄る事は不可能なため、NO
と出力します。
入力例2
1 1 8 2 2 6 1 4 5
出力例2
YES
入力例1と同じ配置ですが、高橋君の移動速度が 6 に変わっています。
高橋君の移動可能距離が 12 になったので、今度は家に寄ることが可能となっています。
よって、YES
と出力します。
入力例3
1 1 8 2 2 5 1 4 5
出力例3
YES
ぴったり移動可能な場合も、寄ること自体は可能なので、YES
と出力します。
入力例4
7 7 1 1 3 4 3 8 1 1 7 9 9
出力例4
YES
2 番目の女の子の家にだけ、寄ることが可能です。