D. Space mines

很久以前，在遥远的星系中... 达斯·维达发现了叛军基地的位置。现在他打算使用死星摧毁该基地（以及基地所在的整个星球）。 当叛军得知死星正在逼近时，他们决定使用他们的新秘密武器——空间地雷。下面描述空间地雷的构造。 每个空间地雷呈球形（称为地雷本体），半径为 #cf_span[r]，中心位于点 #cf_span[O]。从中心伸出若干尖刺。每根尖刺可表示为连接地雷中心 #cf_span[O] 与某点 #cf_span[P] 的线段，满足 （运输长尖刺地雷存在困难），其中 #cf_span[|OP|] 表示连接 #cf_span[O] 和 #cf_span[P] 的线段长度。为方便起见，点 #cf_span[P] 可用向量 #cf_span[p] 描述，使得 #cf_span[P = O + p]。 死星呈球形，半径为 #cf_span[R]（#cf_span[R] 大于任何地雷的半径）。它以恒定速度沿向量 #cf_span[v] 移动，速度大小为 #cf_span[|v|]。当叛军发现死星时，它位于点 #cf_span[A]。 叛军在死星的行进路线上部署了 #cf_span[n] 个空间地雷。可将地雷视为静止不动。死星并不知晓地雷的存在，也无法察觉它们，因此不会改变运动方向。一旦死星接触地雷（其本体或任一根尖刺），地雷就会爆炸并摧毁死星。接触指空间中存在一个点，该点同时属于地雷和死星。若死星能无限长时间移动而不接触任何地雷，则认为其不会被摧毁。 请帮助叛军判断他们是否能利用空间地雷成功摧毁死星。若能成功，请确定从发现死星到爆炸发生的时间点（从发现死星的时刻开始计时）。 第一行输入包含 #cf_span[7] 个整数 #cf_span[Ax, Ay, Az, vx, vy, vz, R]，分别表示死星的初始位置、移动方向和半径（#cf_span[ - 10 ≤ vx, vy, vz ≤ 10]，#cf_span[|v| > 0]，#cf_span[0 < R ≤ 100]）。 第二行包含一个整数 #cf_span[n]，表示地雷数量（#cf_span[1 ≤ n ≤ 100]）。随后是 #cf_span[n] 个数据块，第 #cf_span[i] 个块描述第 #cf_span[i] 个地雷。 每个块的第一行包含 #cf_span[5] 个整数 #cf_span[Oix, Oiy, Oiz, ri, mi]，分别表示地雷中心的坐标、本体半径和尖刺数量（#cf_span[0 < ri < 100，0 ≤ mi ≤ 10]）。随后是 #cf_span[mi] 行，描述第 #cf_span[i] 个地雷的尖刺，其中第 #cf_span[j] 行描述第 #cf_span[i] 个地雷的第 #cf_span[j] 根尖刺，包含 #cf_span[3] 个整数 #cf_span[pijx, pijy, pijz] —— 表示该尖刺方向的向量坐标（）。 地雷中心与死星中心的坐标均为整数，其绝对值不超过 #cf_span[10000]。保证对任意 #cf_span[1 ≤ i ≤ n]，有 #cf_span[R > ri]。对任意两个不同地雷 #cf_span[i ≠ j]，满足以下不等式： 。初始时刻，死星与所有地雷无公共点。 若叛军能成功利用空间地雷摧毁死星，请输出从发现死星到爆炸发生的时间。 若死星不会接触任何地雷，请输出 "-1"（不含引号）。 答案的绝对或相对误差允许在 #cf_span[10 - 6] 范围内。 ## Input 第一行输入包含 #cf_span[7] 个整数 #cf_span[Ax, Ay, Az, vx, vy, vz, R]，分别表示死星的初始位置、移动方向和半径（#cf_span[ - 10 ≤ vx, vy, vz ≤ 10]，#cf_span[|v| > 0]，#cf_span[0 < R ≤ 100]）。第二行包含一个整数 #cf_span[n]，表示地雷数量（#cf_span[1 ≤ n ≤ 100]）。随后是 #cf_span[n] 个数据块，第 #cf_span[i] 个块描述第 #cf_span[i] 个地雷。每个块的第一行包含 #cf_span[5] 个整数 #cf_span[Oix, Oiy, Oiz, ri, mi]，分别表示地雷中心的坐标、本体半径和尖刺数量（#cf_span[0 < ri < 100，0 ≤ mi ≤ 10]）。随后是 #cf_span[mi] 行，描述第 #cf_span[i] 个地雷的尖刺，其中第 #cf_span[j] 行描述第 #cf_span[i] 个地雷的第 #cf_span[j] 根尖刺，包含 #cf_span[3] 个整数 #cf_span[pijx, pijy, pijz] —— 表示该尖刺方向的向量坐标（）。地雷中心与死星中心的坐标均为整数，其绝对值不超过 #cf_span[10000]。保证对任意 #cf_span[1 ≤ i ≤ n]，有 #cf_span[R > ri]。对任意两个不同地雷 #cf_span[i ≠ j]，满足以下不等式： 。初始时刻，死星与所有地雷无公共点。 ## Output 若叛军能成功利用空间地雷摧毁死星，请输出从发现死星到爆炸发生的时间。若死星不会接触任何地雷，请输出 "-1"（不含引号）。答案的绝对或相对误差允许在 #cf_span[10 - 6] 范围内。 [samples]

**Definitions:** - Let $\mathbf{A} = (A_x, A_y, A_z) \in \mathbb{R}^3$ be the initial position of the center of the Death Star at time $t = 0$. - Let $\mathbf{v} = (v_x, v_y, v_z) \in \mathbb{R}^3$ be the constant velocity vector of the Death Star, with $\|\mathbf{v}\| > 0$. - Let $R > 0$ be the radius of the Death Star. - The position of the Death Star’s center at time $t \geq 0$ is: $$ \mathbf{C}(t) = \mathbf{A} + t \mathbf{v}. $$ - The Death Star is the closed ball: $$ \mathcal{D}(t) = \left\{ \mathbf{x} \in \mathbb{R}^3 : \|\mathbf{x} - \mathbf{C}(t)\| \leq R \right\}. $$ - There are $n$ space mines. For mine $i$ ($1 \leq i \leq n$): - Let $\mathbf{O}_i = (O_{ix}, O_{iy}, O_{iz}) \in \mathbb{R}^3$ be the center of the mine body. - Let $r_i > 0$ be the radius of the mine body. - Let $m_i \in \mathbb{Z}_{\geq 0}$ be the number of spikes. - For each spike $j \in \{1, \dots, m_i\}$, let $\mathbf{p}_{ij} = (p_{ijx}, p_{ijy}, p_{ijz}) \in \mathbb{R}^3$ be the vector from $\mathbf{O}_i$ to the spike tip, with $\|\mathbf{p}_{ij}\| \leq r_i$. - The mine body is the closed ball: $$ \mathcal{B}_i = \left\{ \mathbf{x} \in \mathbb{R}^3 : \|\mathbf{x} - \mathbf{O}_i\| \leq r_i \right\}. $$ - The $j$-th spike is the line segment: $$ \mathcal{S}_{ij} = \left\{ \mathbf{O}_i + s \mathbf{p}_{ij} : s \in [0, 1] \right\}. $$ - The full mine $i$ is the union: $$ \mathcal{M}_i = \mathcal{B}_i \cup \bigcup_{j=1}^{m_i} \mathcal{S}_{ij}. $$ **Constraints:** - $\|\mathbf{v}\| > 0$. - $R > r_i$ for all $i$. - At $t = 0$, $\mathcal{D}(0) \cap \mathcal{M}_i = \emptyset$ for all $i$. - All coordinates are integers; $\|\mathbf{p}_{ij}\| \leq r_i$. **Objective:** Find the smallest $t^* \geq 0$ such that $$ \mathcal{D}(t^*) \cap \mathcal{M}_i \neq \emptyset \quad \text{for some } i \in \{1, \dots, n\}. $$ If no such $t^*$ exists, return $-1$. --- **Mathematical Formulation:** Compute $$ t^* = \min_{i=1}^n \min \left\{ t \geq 0 : \mathcal{D}(t) \cap \mathcal{M}_i \neq \emptyset \right\}, $$ where for each mine $i$, $$ \min \left\{ t \geq 0 : \mathcal{D}(t) \cap \mathcal{M}_i \neq \emptyset \right\} = \min \left( \min_{j=0}^{m_i} \min \left\{ t \geq 0 : \mathcal{D}(t) \cap \mathcal{K}_{ij} \neq \emptyset \right\} \right), $$ with $\mathcal{K}_{i0} = \mathcal{B}_i$ (mine body), and $\mathcal{K}_{ij} = \mathcal{S}_{ij}$ for $j = 1, \dots, m_i$. For each geometric object $\mathcal{K} \in \{ \mathcal{B}_i, \mathcal{S}_{i1}, \dots, \mathcal{S}_{im_i} \}$, solve: $$ \min \left\{ t \geq 0 : \text{dist}(\mathbf{C}(t), \mathcal{K}) \leq R \right\}, $$ where $\text{dist}(\mathbf{C}(t), \mathcal{K}) = \inf_{\mathbf{x} \in \mathcal{K}} \|\mathbf{C}(t) - \mathbf{x}\|$. - For the mine body $\mathcal{B}_i$: $$ \text{dist}(\mathbf{C}(t), \mathcal{B}_i) = \max\left(0, \|\mathbf{C}(t) - \mathbf{O}_i\| - r_i\right). $$ Solve: $$ \|\mathbf{A} + t\mathbf{v} - \mathbf{O}_i\| \leq R + r_i, \quad t \geq 0. $$ - For a spike $\mathcal{S}_{ij}$: Let $\mathbf{L}_{ij}(s) = \mathbf{O}_i + s \mathbf{p}_{ij}, s \in [0,1]$. Then: $$ \text{dist}(\mathbf{C}(t), \mathcal{S}_{ij}) = \min_{s \in [0,1]} \|\mathbf{A} + t\mathbf{v} - \mathbf{O}_i - s \mathbf{p}_{ij}\|. $$ This is the distance from point $\mathbf{C}(t)$ to the line segment $\mathcal{S}_{ij}$. Solve: $$ \min_{s \in [0,1]} \|\mathbf{A} + t\mathbf{v} - \mathbf{O}_i - s \mathbf{p}_{ij}\| \leq R. $$ For each of these (body and spikes), solve the resulting non-linear (quadratic) inequality in $t$, find the minimal non-negative root, and take the global minimum over all $i$ and all components. If no solution exists for any mine, output $-1$. Otherwise, output the smallest such $t^*$. --- **Final Output:** $$ \boxed{t^* = \min_{\substack{1 \leq i \leq n \\ 0 \leq j \leq m_i}} \min \left\{ t \geq 0 : \text{dist}(\mathbf{A} + t\mathbf{v}, \mathcal{K}_{ij}) \leq R \right\}} $$ where $\mathcal{K}_{i0} = \mathcal{B}_i$, $\mathcal{K}_{ij} = \mathcal{S}_{ij}$ for $j \geq 1$. If the set of feasible $t$ is empty for all $i,j$, output $-1$.