QOJ.ac

QOJ

時間限制: 1 s 記憶體限制: 1024 MB 總分: 100

#2394. 避开小行星

统计

你逃离了行星,但敌方星际战斗机就在你身后!更糟糕的是,在你和基地安全区之间有一个小行星带。星际战斗机绝不会跟随你进入小行星带,但不幸的是,你在逃生过程中耗尽了所有燃料,只剩下一小滴,仅够引擎进行最后一次爆发。你有两个选择:你可以投降并面临漫长的刑期;或者,你可以将星舰瞄准基地,并进行那最后一次爆发。你无法预知这次爆发会让你以多快的速度前进,但你知道它最终会把你带到基地的安全区。当然,前提是你没有撞上任何小行星。

你拥有小行星带的扫描图,需要确定你是否肯定有一条穿过该区域的安全路线,或者投降是否是更好的选择。一些重要的注意事项:

  • 你的飞船和基地相对于小行星的大小而言微不足道,可以视为点。
  • 你对小行星的扫描将给出质心、运动方向(质心的运动方向)以及小行星凸包上的点(均在扫描时测量)。
  • 每颗小行星的质心随时间沿给定方向平移,但速度未知。(你知道速度是非负的:小行星不会向后移动。)
  • 小行星可以绕其质心向任意方向、以任意角速度旋转。你没有任何关于小行星翻滚的信息,必须考虑所有可能性。
  • 小行星之间不会反弹(如果它们发生碰撞,请将小行星视为彼此穿过)。
  • 如果你决定不投降,你的飞船将以未知的速度穿过小行星带:可能极慢,也可能极快。你无法控制飞船的速度,也无法绕过小行星。
  • 你可以假设没有小行星会“擦过”飞船。形式上,对于每颗小行星,以下两者必居其一:
    1. 对于你的飞船速度、小行星速度和小行星角速度的任何组合,你的飞船与小行星之间的距离至少为 $10^{-6}$ 个单位,或者
    2. 存在某种你的飞船速度、小行星速度和小行星角速度的组合,使得你的飞船与小行星相交,且你的飞船与小行星表面最近点之间的距离至少为 $10^{-6}$ 个单位。
  • 没有任何小行星会与你的基地发生碰撞(或擦过):对于小行星速度和角速度的任何组合,你的基地与小行星之间的距离在任何时候都至少为 $10^{-6}$ 个单位。
  • 你的飞船起始位置距离基地至少 $10^{-6}$ 个单位。

输入格式

输入的第一行包含六个实数 $s_x, s_y, s_z, b_x, b_y, b_z$ 和一个整数 $n$,以空格分隔。这些给出了你的飞船的 3D 坐标 $(s_x, s_y, s_z)$、基地的 3D 坐标 $(b_x, b_y, b_z)$ 以及小行星的数量 $n$ ($0 \le n \le 30$)。

接下来的 $2n$ 行描述了每颗小行星,每两行描述一颗小行星。每对的第一行包含六个实数 $p_x, p_y, p_z, d_x, d_y, d_z$ 和一个整数 $m$,以空格分隔,给出了小行星质心的位置 $(p_x, p_y, p_z)$ 和方向 $(d_x, d_y, d_z)$,以及小行星凸包上的点数 $m$ ($4 \le m \le 8$)。每对的第二行包含 $3m$ 个实数,给出了 $m$ 个点的三元组 $c_{i,x}, c_{i,y}, c_{i,z}$,均以空格分隔。这些是扫描时小行星凸包上点的 3D 坐标。小行星质心位于凸包内的某个位置(不一定是几何中心)。

输入中的所有实数都在范围 $[-2 \cdot 10^6, 2 \cdot 10^6]$ 内,且小数点后最多有 6 位数字。每颗小行星的方向都是一个单位向量(在数值容差范围内),并将满足 $\left| \sqrt{d_x^2 + d_y^2 + d_z^2} - 1 \right| \le 10^{-6}$。

输出格式

如果你保证有一条穿过小行星带的安全路线,则打印 Go。否则,打印 Surrender

样例

样例输入 1

10.0 0.0 0.0 0.0 0.0 0.0 1
5.0 3.0 0.0 0.0 -1.0 0.0 6
7.0 3.0 0.0 3.0 3.0 0.0 5.0 1.0 0.0 5.0 5.0 0.0 5.0 3.0 1.0 5.0 3.0 -1.0

样例输出 1

Surrender

样例输入 2

10.0 0.0 0.0 0.0 0.0 0.0 1
5.0 3.0 0.0 0.0 1.0 0.0 6
7.0 3.0 0.0 3.0 3.0 0.0 5.0 1.0 0.0 5.0 5.0 0.0 5.0 3.0 1.0 5.0 3.0 -1.0

样例输出 2

Go

样例输入 3

10.0 0.0 0.0 0.0 0.0 0.0 1
15.0 0.0 0.0 1.0 0.0 0.0 6
14.0 0.0 0.0 16.0 0.0 0.0 15.0 1.0 0.0 15.0 -1.0 0.0 15.0 0.0 1.0 15.0 0.0 -1.0

样例输出 3

Go

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.