300341: CF65C. Harry Potter and the Golden Snitch

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Harry Potter and the Golden Snitch

题意翻译

## 题目描述 弗雷德和乔治 $·$ 韦斯莱两兄弟曾经进入了一个体育用品商店并打开了一盒魁地奇球。在漫长而痛苦的实验后,他们发现金色飞贼根本就没有被施过魔法:它只是一个被编了程的装置。它总是沿着同一个轨迹——一个顶点在 $ (x_0, y_0, z_0) $,$ (x_1, y_1, z_1) $……$ (x_n, y_n, z_n) $的折线——移动。 在比赛开始时飞贼被放在点 $ (x_0, y_0, z_0) $,然后以恒定的速度$ v_s $在折线上移动。双胞胎暂时还没发现在那之后飞贼的行为。尽管如此,他们仍希望收集回来的信息能够帮助哈利 $·$ 波特和他的队伍在即将到来的与斯莱特林的比赛中胜出。哈利$·$波特得知在比赛开始时他会在 $ (P_x,P_y,P_z) $,而他那超快的光轮 $ 2011 $ 允许他以恒定的速度 $ v_p $ 向任何方向移动或保持静止。$ v_p $ 不小于飞贼的速度 $ v_s $ 。 哈利 $·$ 波特当然想要尽快抓住飞贼。如果他能在折线上抓住飞贼,他想督促韦斯莱兄弟继续进行实验。当哈利 $·$ 波特和飞贼在同一坐标时,他就能抓住飞贼。 ## 输入格式 第一行为一个整数 $ n(1 <= n <=10000)$ 。接下来的 $ n+1 $ 行为坐标 $ (x_i,y_i,z_i) $,被单个空格隔开。任意两个相连的点坐标不会相同。下一行为速度 $ v_p $ ,$ v_s $。最后一行为 $ (P_x,P_y,P_z)$,被单个空格隔开。 输入的所有数字均为绝对值不超过 $ 10^4 $ 的整数。速度均为正数,且数据保证 $ v_s \le v_p $。 ## 输出格式 如果哈利 $·$ 波特能在折线上抓住飞贼——包括终点 $(x_n, y_n, z_n)$,第一行输出 $ “YES” $(不包括引号)。在第二行输出哈利能够抓住飞贼的最早时间t。在第三行输出三个数字 $ X,Y,Z $,即抓住飞贼的位置。‘ 相对或绝对误差不得超过 $10^{-6}$ 如果哈利没法在飞贼沿着所描述的折线运动时抓住它,输出 $ “NO” $。

题目描述

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.

输入输出格式

输入格式


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 $ 10^{4} $ . The speeds are strictly positive. It is guaranteed that $ v_{s}<=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".

输入输出样例

输入样例 #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

Input

题意翻译

## 题目描述 弗雷德和乔治 $·$ 韦斯莱两兄弟曾经进入了一个体育用品商店并打开了一盒魁地奇球。在漫长而痛苦的实验后,他们发现金色飞贼根本就没有被施过魔法:它只是一个被编了程的装置。它总是沿着同一个轨迹——一个顶点在 $ (x_0, y_0, z_0) $,$ (x_1, y_1, z_1) $……$ (x_n, y_n, z_n) $的折线——移动。 在比赛开始时飞贼被放在点 $ (x_0, y_0, z_0) $,然后以恒定的速度$ v_s $在折线上移动。双胞胎暂时还没发现在那之后飞贼的行为。尽管如此,他们仍希望收集回来的信息能够帮助哈利 $·$ 波特和他的队伍在即将到来的与斯莱特林的比赛中胜出。哈利$·$波特得知在比赛开始时他会在 $ (P_x,P_y,P_z) $,而他那超快的光轮 $ 2011 $ 允许他以恒定的速度 $ v_p $ 向任何方向移动或保持静止。$ v_p $ 不小于飞贼的速度 $ v_s $ 。 哈利 $·$ 波特当然想要尽快抓住飞贼。如果他能在折线上抓住飞贼,他想督促韦斯莱兄弟继续进行实验。当哈利 $·$ 波特和飞贼在同一坐标时,他就能抓住飞贼。 ## 输入格式 第一行为一个整数 $ n(1 <= n <=10000)$ 。接下来的 $ n+1 $ 行为坐标 $ (x_i,y_i,z_i) $,被单个空格隔开。任意两个相连的点坐标不会相同。下一行为速度 $ v_p $ ,$ v_s $。最后一行为 $ (P_x,P_y,P_z)$,被单个空格隔开。 输入的所有数字均为绝对值不超过 $ 10^4 $ 的整数。速度均为正数,且数据保证 $ v_s \le v_p $。 ## 输出格式 如果哈利 $·$ 波特能在折线上抓住飞贼——包括终点 $(x_n, y_n, z_n)$,第一行输出 $ “YES” $(不包括引号)。在第二行输出哈利能够抓住飞贼的最早时间t。在第三行输出三个数字 $ X,Y,Z $,即抓住飞贼的位置。‘ 相对或绝对误差不得超过 $10^{-6}$ 如果哈利没法在飞贼沿着所描述的折线运动时抓住它,输出 $ “NO” $。

加入题单

上一题 下一题 算法标签: