CF65C.Harry Potter and the Golden Snitch

提高+/省选-

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Brothers Fred and George Weasley once got into the sporting goods store and opened a box of Quidditch balls. After long and painful experiments they found out that the Golden Snitch is not enchanted at all. It is simply a programmed device. It always moves along the same trajectory, which is a polyline with vertices at the points (_x_0, _y_0, _z_0), (_x_1, _y_1, _z_1), ..., (x__n, y__n, z__n). At the beginning of the game the snitch is positioned at the point (_x_0, _y_0, _z_0), and then moves along the polyline at the constant speed v__s. The twins have not yet found out how the snitch behaves then. Nevertheless, they hope that the retrieved information will help Harry Potter and his team in the upcoming match against Slytherin. Harry Potter learned that at the beginning the game he will be at the point (P__x, P__y, P__z) and his super fast Nimbus 2011 broom allows him to move at the constant speed v__p in any direction or remain idle. v__p is not less than the speed of the snitch v__s. Harry Potter, of course, wants to catch the snitch as soon as possible. Or, if catching the snitch while it is moving along the polyline is impossible, he wants to hurry the Weasley brothers with their experiments. Harry Potter catches the snitch at the time when they are at the same point. Help Harry.

双胞胎兄弟弗雷德和乔治·韦斯莱曾闯入一家体育用品商店,打开了一盒魁地奇球。经过漫长而痛苦的实验,他们发现金色飞贼其实根本未被施加魔法,它仅仅是一个编程设备。它始终沿着同一条轨迹运动,该轨迹是一条折线,其顶点依次为点 (x0, y0, z0)(x_0,\,y_0,\,z_0)、(x1, y1, z1)(x_1,\,y_1,\,z_1)、…、(xn, yn, zn)(x_n,\,y_n,\,z_n)。比赛开始时,飞贼位于点 (x0, y0, z0)(x_0,\,y_0,\,z_0),随后以恒定速度 vsv_s 沿该折线运动。双胞胎尚未弄清飞贼此后的行为方式。尽管如此,他们仍希望所获取的信息能帮助哈利·波特及其队友在即将到来的对阵斯莱特林队的比赛中取得优势。
哈利·波特得知,比赛开始时他将位于点 (Px, Py, Pz)(P_x,\,P_y,\,P_z),而他那把超快的“光轮2011”扫帚允许他以恒定速度 vpv_p 向任意方向移动,或保持静止不动。其中 vpv_p 不小于飞贼的速度 vsv_s。哈利·波特当然希望尽快抓住飞贼;若在飞贼沿该折线运动期间无法抓到它,则他希望尽快敦促韦斯莱兄弟加快他们的实验进度。当哈利与飞贼处于同一位置时,即视为哈利成功抓住飞贼。请帮助哈利。

输入格式

The first line contains a single integer n (1 ≤ n ≤ 10000). The following n + 1 lines contain the coordinates x__i, y__i, z__i, separated by single spaces. The coordinates of any two consecutive points do not coincide. The next line contains the velocities v__p and v__s, the last line contains P__x, P__y, P__z, separated by single spaces. All the numbers in the input are integers, their absolute value does not exceed 104. The speeds are strictly positive. It is guaranteed that v__s ≤ v__p.

第一行包含一个整数 nn(1≤n≤100001 \leq n \leq 10000)。接下来的 n+1n+1 行每行包含三个坐标 xix_i、yiy_i、ziz_i,以单个空格分隔。任意两个相邻点的坐标互不相同。随后一行包含速度 vpv_p 和 vsv_s,最后一行包含 PxP_x、PyP_y、PzP_z,以单个空格分隔。输入中的所有数字均为整数,其绝对值不超过 10410^4。速度严格为正。保证 vs≤vpv_s \leq v_p。

输出格式

If Harry Potter can catch the snitch while it is moving along the polyline (including the end (x__n, y__n, z__n)), print "YES" in the first line (without the quotes). Print in the second line t, which is the earliest moment of time, when Harry will be able to catch the snitch. On the third line print three numbers X, Y, Z, the coordinates of the point at which this happens. The absolute or relative error in the answer should not exceed 10 - 6. If Harry is not able to catch the snitch during its moving along the described polyline, print "NO".

如果哈利·波特能在飞贼沿折线运动的过程中(包括终点 (xn,yn,zn)(x_n, y_n, z_n))抓住它,则在第一行输出 "YES"(不带引号)。在第二行输出 tt,即哈利最早能够抓住飞贼的时刻。在第三行输出三个数 XX、YY、ZZ,表示该事件发生的坐标点。答案的绝对或相对误差不得超过 10−610^{-6}。若哈利在飞贼沿所述折线运动的整个过程中都无法抓住它,则输出 "NO"。

输入输出样例

  • 输入#1

    4
    0 0 0
    0 10 0
    10 10 0
    10 0 0
    0 0 0
    1 1
    5 5 25

    输出#1

    YES
    25.5000000000
    10.0000000000 4.5000000000 0.0000000000
  • 输入#2

    4
    0 0 0
    0 10 0
    10 10 0
    10 0 0
    0 0 0
    1 1
    5 5 50

    输出#2

    NO
  • 输入#3

    1
    1 2 3
    4 5 6
    20 10
    1 2 3

    输出#3

    YES
    0.0000000000
    1.0000000000 2.0000000000 3.0000000000

输入解题思路,AI测评打分。不知道怎么写?

首页