← 返回题目列表

Codeforces · 89/D

D. 太空地雷

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

曾几何时,在遥远的银河系……

达斯·韦德发现了叛军基地的位置。现在他要使用死星摧毁基地(以及基地所在的整个星球)。

当叛军得知死星即将到来时,他们决定使用他们的新秘密武器——太空地雷。让我们来描述一下太空地雷的建造。

每个太空地雷的形状都是一个以O点为中心、半径为r的球体(我们称之为地雷体),从中心突出有几个尖刺。每个尖峰可以表示为一个线段,将矿井中心与某个点 P 连接起来,使得 $$r < |OP| \leq \frac{3}{2}r$$ (运输长尖刺地雷是有问题的),其中 |OP|是连接 O 和 P 的线段的长度。用向量 p 来描述点 P 很方便,使得 P = O + p。

死星的形状像一个半径为 R 的球(R 超过任何地雷的半径)。它以等于|v|的速度沿v矢量匀速移动。叛军注意到死亡之星的那一刻,它就位于A点。

叛军沿着死星布设了 n 个太空地雷。你可能会认为这些矿井是闲置的。死星不知道地雷的存在,也无法注意到它们,这就是为什么它不会改变其运动方向。一旦死亡之星接触到地雷(其本体或其中一根尖刺),地雷就会爆炸并摧毁死亡之星。接触是指空间中有一个点既属于矿井又属于死星的情况。人们认为,如果死星能够无限长时间移动而不接触地雷,它就不会被摧毁。

帮助叛军确定他们是否能够使用太空地雷成功摧毁死星。如果他们会成功,请确定它发生的时间(从注意到死星的那一刻开始)。

输入

第一个输入数据行包含 7 个整数 Ax、Ay、Az、vx、vy、vz、R。它们是死星的初始位置、运动方向和半径(- 10 ≤ vx、vy、vz ≤ 10、|v| > 0、0 < R ≤ 100)。

第二行包含一个整数n,它是地雷的数量(1 ≤ n ≤ 100)。然后跟随n个数据块,其中第i个描述第i个矿井。

每个区块的第一行包含 5 个整数 Oix、Oiy、Oiz、ri、mi,分别是地雷中心坐标、矿体半径和尖峰数量(0 < ri < 100, 0 ≤ mi ≤ 10)。然后沿着 mi 行,描述第 i 个地雷的尖峰,其中第 j 个描述第 i 个尖峰,并包含 3 个整数 pijx、pijy、pijz — 给定尖峰所指向的向量的坐标 ($$r_{i} < | p_{ij} | \leq \frac{3}{2} r_{i}$$)。

地雷中心和死星中心的坐标均为整数,其绝对值不超过10000。对于任意1 ≤ i ≤ n,保证R > ri。对于任何地雷 i ≠ j,如果满足以下不等式:$$|O_i O_j| > \frac{3}{2}(r_i + r_j)$$。最初死星和地雷没有共同点。

输出

如果叛军成功使用太空地雷阻止死星,请打印从发现死星到爆炸的时间。

如果死星不会触雷,则打印“-1”(不带引号)。

对于答案,10 - 6 的绝对或相对误差是可以接受的。

示例

输入 #1

0 0 0 1 0 0 5
2
10 8 0 2 2
0 -3 0
2 2 0
20 0 0 4 3
2 4 0
-4 3 0
1 -5 0

输出 #1

10.0000000000

输入 #2

8 8 4 4 4 2 6
1
-2 -2 -1 3 0

输出 #2

-1

输入 #3

30 30 2 1 2 1 20
3
0 0 40 5 1
1 4 4
-10 -40 -5 7 0
100 200 95 8 1
-10 0 0

输出 #3

74.6757620881