UVa 10794 The Deadly Olympic Returns

题目描述

现在是公元100001000010000年。在本题中，我们将讨论一个名为"奥林匹克"的全球性游戏节的恢复，该活动很久以前（二十世纪）曾经举办过。新成立的国际奥林匹克委员会 (IOC\texttt{IOC}IOC)引入了一种类似狗斗的战争格式：双方将带来各自国家空军提供的最佳战机，并装载导弹。在某个时刻，一方会向另一方发射导弹。同时，另一方也会发射导弹以拦截对方的导弹。解说员想在比赛发生前预测结果，他们需要计算两枚导弹之间的最小可能距离。

输入格式：

• 第一行：整数TTT(1≤T≤5001 \leq T \leq 5001≤T≤500) 表示测试用例数量
• 每个测试用例有三行：
  1. 正整数timetimetime
  2. 六个整数x1x_1x1​,y1y_1y1​,z1z_1z1​,x2x_2x2​,y2y_2y2​,z2z_2z2​- 第一枚导弹的起点和终点
  3. 六个整数x3x_3x3​,y3y_3y3​,z3z_3z3​,x4x_4x4​,y4y_4y4​,z4z_4z4​- 第二枚导弹的起点和终点

输出格式：

• 每个测试用例输出一行：Case i: distance，其中distance保留四位小数

样例：

输入： 2 1 0 0 0 1 0 0 0 -1 0 0 -2 0 4 0 0 0 1 0 0 -1 0 0 -2 0 0 输出： Case 1: 1.0000 Case 2: 1.0000

题目分析

问题本质

本题要求计算两枚在三维空间中匀速直线运动的导弹之间的最小距离。这是计算几何中的一个经典问题：求两条线段之间的最小距离。

每枚导弹的运动可以用参数方程表示：

• 第一枚导弹：A(t)=P1+v1⋅t\mathbf{A}(t) = \mathbf{P_1} + \mathbf{v_1} \cdot tA(t)=P1​+v1​⋅t
• 第二枚导弹：B(t)=P2+v2⋅t\mathbf{B}(t) = \mathbf{P_2} + \mathbf{v_2} \cdot tB(t)=P2​+v2​⋅t

其中：

• P1=(x1,y1,z1)\mathbf{P_1} = (x_1, y_1, z_1)P1​=(x1​,y1​,z1​),P2=(x3,y3,z3)\mathbf{P_2} = (x_3, y_3, z_3)P2​=(x3​,y3​,z3​)是起点
• v1=(x2−x1,y2−y1,z2−z1)time\mathbf{v_1} = \frac{(x_2-x_1, y_2-y_1, z_2-z_1)}{time}v1​=time(x2​−x1​,y2​−y1​,z2​−z1​)​,v2=(x4−x3,y4−y3,z4−z3)time\mathbf{v_2} = \frac{(x_4-x_3, y_4-y_3, z_4-z_3)}{time}v2​=time(x4​−x3​,y4​−y3​,z4​−z3​)​是速度向量
• t∈[0,time]t \in [0, time]t∈[0,time]是时间参数

我们需要计算：min⁡t∈[0,time]∥A(t)−B(t)∥\min\limits_{t \in [0, time]} \|\mathbf{A}(t) - \mathbf{B}(t)\|t∈[0,time]min​∥A(t)−B(t)∥

数学推导

设相对位置向量为：
R(t)=B(t)−A(t)=(P2−P1)+(v2−v1)⋅t\mathbf{R}(t) = \mathbf{B}(t) - \mathbf{A}(t) = (\mathbf{P_2} - \mathbf{P_1}) + (\mathbf{v_2} - \mathbf{v_1}) \cdot tR(t)=B(t)−A(t)=(P2​−P1​)+(v2​−v1​)⋅t

距离的平方为：
D2(t)=∥R(t)∥2=∥P+V⋅t∥2D^2(t) = \|\mathbf{R}(t)\|^2 = \|\mathbf{P} + \mathbf{V} \cdot t\|^2D2(t)=∥R(t)∥2=∥P+V⋅t∥2

其中：

• P=P2−P1\mathbf{P} = \mathbf{P_2} - \mathbf{P_1}P=P2​−P1​（初始相对位置）
• V=v2−v1\mathbf{V} = \mathbf{v_2} - \mathbf{v_1}V=v2​−v1​（相对速度）

展开得：
D2(t)=(V⋅V)t2+2(P⋅V)t+(P⋅P)D^2(t) = (\mathbf{V} \cdot \mathbf{V}) t^2 + 2(\mathbf{P} \cdot \mathbf{V}) t + (\mathbf{P} \cdot \mathbf{P})D2(t)=(V⋅V)t2+2(P⋅V)t+(P⋅P)

这是一个关于ttt的二次函数，开口向上（因为V⋅V≥0\mathbf{V} \cdot \mathbf{V} \geq 0V⋅V≥0）。最小值可能出现在：

1. 区间内部：t0=−P⋅VV⋅Vt_0 = -\frac{\mathbf{P} \cdot \mathbf{V}}{\mathbf{V} \cdot \mathbf{V}}t0​=−V⋅VP⋅V​（当V⋅V≠0\mathbf{V} \cdot \mathbf{V} \neq 0V⋅V=0）
2. 区间端点：t=0t = 0t=0或t=timet = timet=time

更巧妙的解法：相对运动参考系

AC 代码使用了一个更巧妙的解法：变换参考系。

如果让第一枚导弹变为静止，那么问题就转化为：求一个固定点（第一枚导弹）到一条动直线（第二枚导弹的相对轨迹）的最短距离。

在新的参考系中：

• 第一枚导弹位置为原点(0,0,0)(0, 0, 0)(0,0,0)
• 第二枚导弹的轨迹为：R(t)=P+V⋅t\mathbf{R}(t) = \mathbf{P} + \mathbf{V} \cdot tR(t)=P+V⋅t
• 其中P=P2−P1\mathbf{P} = \mathbf{P_2} - \mathbf{P_1}P=P2​−P1​，V=v2−v1\mathbf{V} = \mathbf{v_2} - \mathbf{v_1}V=v2​−v1​

这样，最小距离就等于原点到直线R(t)\mathbf{R}(t)R(t)的距离。

点到直线的距离公式为：
d=∥P×V∥∥V∥d = \frac{\|\mathbf{P} \times \mathbf{V}\|}{\|\mathbf{V}\|}d=∥V∥∥P×V∥​

其中×\times×表示向量叉积。

推导：
点到直线上任意点的向量为P+Vt\mathbf{P} + \mathbf{V}tP+Vt，其长度平方为：
f(t)=∥P+Vt∥2=∥P∥2+2(P⋅V)t+∥V∥2t2f(t) = \|\mathbf{P} + \mathbf{V}t\|^2 = \|\mathbf{P}\|^2 + 2(\mathbf{P} \cdot \mathbf{V})t + \|\mathbf{V}\|^2 t^2f(t)=∥P+Vt∥2=∥P∥2+2(P⋅V)t+∥V∥2t2

最小值在t0=−P⋅V∥V∥2t_0 = -\frac{\mathbf{P} \cdot \mathbf{V}}{\|\mathbf{V}\|^2}t0​=−∥V∥2P⋅V​处取得，此时：
f(t0)=∥P∥2−(P⋅V)2∥V∥2f(t_0) = \|\mathbf{P}\|^2 - \frac{(\mathbf{P} \cdot \mathbf{V})^2}{\|\mathbf{V}\|^2}f(t0​)=∥P∥2−∥V∥2(P⋅V)2​

根据向量恒等式∥a×b∥2=∥a∥2∥b∥2−(a⋅b)2\|\mathbf{a} \times \mathbf{b}\|^2 = \|\mathbf{a}\|^2 \|\mathbf{b}\|^2 - (\mathbf{a} \cdot \mathbf{b})^2∥a×b∥2=∥a∥2∥b∥2−(a⋅b)2，得：
f(t0)=∥P×V∥2∥V∥2f(t_0) = \frac{\|\mathbf{P} \times \mathbf{V}\|^2}{\|\mathbf{V}\|^2}f(t0​)=∥V∥2∥P×V∥2​

所以d=f(t0)=∥P×V∥∥V∥d = \sqrt{f(t_0)} = \frac{\|\mathbf{P} \times \mathbf{V}\|}{\|\mathbf{V}\|}d=f(t0​)​=∥V∥∥P×V∥​

特殊情况处理

1. 相对速度为零（V=0\mathbf{V} = \mathbf{0}V=0）：两导弹相对静止，距离为常数∥P∥\|\mathbf{P}\|∥P∥
2. 点在直线上：距离为000
3. 投影点在直线起点之前（t0≤0t_0 \leq 0t0​≤0）：最小距离出现在t=0t = 0t=0，即∥P∥\|\mathbf{P}\|∥P∥
4. 投影点在直线终点之后（t0≥timet_0 \geq timet0​≥time）：需要考虑t=timet = timet=time的情况

在实际实现中，我们只需要使用点到直线的距离公式，它会自动处理这些情况。

解题思路

算法步骤

1. 读取输入：对于每个测试用例，读取时间timetimetime和两枚导弹的起点终点坐标
2. 计算速度向量：
   • v1=(P1end−P1start)/time\mathbf{v_1} = (\mathbf{P_1^{end}} - \mathbf{P_1^{start}}) / timev1​=(P1end​−P1start​)/time
   • v2=(P2end−P2start)/time\mathbf{v_2} = (\mathbf{P_2^{end}} - \mathbf{P_2^{start}}) / timev2​=(P2end​−P2start​)/time
3. 计算相对向量：
   • P=P2start−P1start\mathbf{P} = \mathbf{P_2^{start}} - \mathbf{P_1^{start}}P=P2start​−P1start​（初始相对位置）
   • V=v2−v1\mathbf{V} = \mathbf{v_2} - \mathbf{v_1}V=v2​−v1​（相对速度）
4. 计算点到直线的距离：
   • 如果∥V∥2\|\mathbf{V}\|^2∥V∥2接近000，返回∥P∥\|\mathbf{P}\|∥P∥
   • 否则，计算d=∥P×V∥∥V∥d = \frac{\|\mathbf{P} \times \mathbf{V}\|}{\|\mathbf{V}\|}d=∥V∥∥P×V∥​
5. 输出结果，保留四位小数

时间复杂度

每个测试用例只需常数次向量运算，时间复杂度为O(1)O(1)O(1)，总复杂度为O(T)O(T)O(T)，其中T≤500T \leq 500T≤500，完全可行。

空间复杂度

只需存储几个三维向量，空间复杂度为O(1)O(1)O(1)。

注意事项

1. 精度问题：使用double类型，比较时使用适当的 epsilon（如10−1210^{-12}10−12）
2. 除以零：当相对速度为零时，需要特殊处理
3. 输出格式：严格按照要求输出，包括 "Case i: " 和四位小数

代码实现

// The Deadly Olympic Returns// UVa ID: 10794// Verdict: Accepted// Submission Date: 2025-12-17// UVa Run Time: 0.000s//// 版权所有（C）2025，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;// 三维点/向量结构体structPoint3D{doublex,y,z;Point3D(doublex=0,doubley=0,doublez=0):x(x),y(y),z(z){}// 从输入读取坐标voidread(){cin>>x>>y>>z;}// 向量加法Point3Doperator+(constPoint3D&other)const{returnPoint3D(x+other.x,y+other.y,z+other.z);}// 向量减法Point3Doperator-(constPoint3D&other)const{returnPoint3D(x-other.x,y-other.y,z-other.z);}// 向量数乘Point3Doperator*(doublescalar)const{returnPoint3D(x*scalar,y*scalar,z*scalar);}// 向量数除Point3Doperator/(doublescalar)const{returnPoint3D(x/scalar,y/scalar,z/scalar);}};// 计算向量的点积doubledotProduct(constPoint3D&a,constPoint3D&b){returna.x*b.x+a.y*b.y+a.z*b.z;}// 计算向量的叉积Point3DcrossProduct(constPoint3D&a,constPoint3D&b){returnPoint3D(a.y*b.z-a.z*b.y,// x分量a.z*b.x-a.x*b.z,// y分量a.x*b.y-a.y*b.x// z分量);}// 计算向量长度的平方doublelengthSquared(constPoint3D&v){returndotProduct(v,v);}// 计算向量长度doublelength(constPoint3D&v){returnsqrt(lengthSquared(v));}// 计算点p到通过点a方向为dir的直线的距离doublepointToLineDistance(constPoint3D&p,constPoint3D&a,constPoint3D&dir){// 如果方向向量长度为0，退化为点到点的距离if(lengthSquared(dir)<1e-12){returnlength(p-a);}// 向量ap = p - aPoint3D ap=p-a;// 计算投影长度比例 t = (ap·dir) / (dir·dir)// 但这里我们不需要计算t，直接使用距离公式// 距离² = |ap|² - (ap·dir)²/|dir|²doubledistSquared=lengthSquared(ap)-pow(dotProduct(ap,dir),2)/lengthSquared(dir);// 防止由于浮点误差导致的负数returnsqrt(max(0.0,distSquared));}intmain(){// 优化输入输出ios::sync_with_stdio(false);cin.tie(nullptr);intt;cin>>t;// 设置输出精度：保留4位小数cout<<fixed<<setprecision(4);for(intcaseNo=1;caseNo<=t;caseNo++){doubletime;cin>>time;// 读取两枚导弹的起点和终点Point3D p1Start,p1End,p2Start,p2End;p1Start.read();p1End.read();p2Start.read();p2End.read();// 计算速度向量 = (终点 - 起点) / 时间Point3D v1=(p1End-p1Start)/time;Point3D v2=(p2End-p2Start)/time;// 相对运动：让第一枚导弹静止// 相对速度 = v2 - v1// 初始相对位置 = p2Start - p1StartPoint3D relativeVelocity=v2-v1;Point3D relativeStart=p2Start-p1Start;// 现在问题转化为：求原点(0,0,0)到直线的距离// 直线方程：L(t) = relativeStart + relativeVelocity * tdoubleminDistance=pointToLineDistance(Point3D(0,0,0),// 原点（第一枚导弹位置）relativeStart,// 直线的起点relativeVelocity// 直线的方向);// 输出结果cout<<"Case "<<caseNo<<": "<<minDistance<<endl;}return0;}

总结

本题是一个典型的三维计算几何问题，关键在于：

1. 理解相对运动：通过参考系变换，将动态问题转化为静态问题
2. 掌握向量运算：点积、叉积、向量长度等基本操作
3. 应用点到直线距离公式：∥a×b∥∥b∥\frac{\|\mathbf{a} \times \mathbf{b}\|}{\|\mathbf{b}\|}∥b∥∥a×b∥​

算法的时间复杂度和空间复杂度都很低，适合处理T≤500T \leq 500T≤500的测试数据。代码实现时需要注意浮点数精度和特殊情况处理。