← 返回题目列表

Codeforces · 65/C

C. 哈利·波特与金色飞贼

中文机器翻译题面 查看原题

弗雷德和乔治韦斯莱兄弟有一次走进体育用品店,打开了一盒魁地奇球。经过漫长而痛苦的实验,他们发现金色飞贼根本没有被施魔法。它只是一个编程设备。它始终沿着相同的轨迹移动,该轨迹是一条顶点位于 (x0, y0, z0), (x1, y1, z1), ..., (xn, yn, zn) 的折线。游戏开始时,飞贼位于点(x0,y0,z0),然后沿着折线匀速移动。双胞胎还没有弄清楚飞贼此时的行为。尽管如此,他们还是希望检索到的信息能够帮助哈利·波特和他的团队在即将到来的对阵斯莱特林的比赛中有所帮助。哈利·波特了解到,在游戏开始时,他将位于点 (Px, Py, Pz),他的超快 Nimbus 2011 扫帚允许他以恒定速度 vp 向任何方向移动或保持闲置。 vp不低于金飞贼对阵哈利·波特的速度,哈利波特当然想尽快抓住金飞贼。或者,如果在飞贼沿着折线移动时抓住它是不可能的,他想催促韦斯莱兄弟进行实验。哈利·波特在他们处于同一位置时抓住了金色飞贼。帮助哈利。

输入

第一行包含一个整数 n (1 ≤ n ≤ 10000)。以下 n + 1 行包含坐标 xi、yi、zi,以单个空格分隔。任意两个连续点的坐标不重合。下一行包含速度 vp 和 vs,最后一行包含 Px、Py、Pz,以单个空格分隔。输入中的所有数字均为整数,其绝对值不超过 104。速度严格为正值。保证vs≤vp。

输出

如果哈利·波特能够在飞贼沿着折线(包括末端 (xn, yn, zn))移动时抓住它,请在第一行中打印“YES”(不带引号)。在第二行中输入 t,这是哈利能够抓住金色飞贼的最早时刻。在第三行打印三个数字 X、Y、Z,即发生这种情况的点的坐标。答案中的绝对或相对误差不应超过 10 - 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