UVa 13056 Jerry‘s Game

题目描述Tom\texttt{Tom}Tom和Jerry\texttt{Jerry}Jerry非常喜欢猫鼠游戏这想必很明显。今天它们玩一个非常复杂的游戏。目标一如既往的简单Jerry\texttt{Jerry}Jerry会跑Tom\texttt{Tom}Tom必须抓住Jerry\texttt{Jerry}Jerry。今天Jerry\texttt{Jerry}Jerry在一个半径为RRR米的完美圆形轨道上以恒定速度V m/sV \, \text{m/s}Vm/s奔跑。开始时Tom\texttt{Tom}Tom坐在圆心处。他想尽快抓住Jerry\texttt{Jerry}Jerry但众所周知Tom\texttt{Tom}Tom不太聪明。他没有计算最优的追赶方向而是始终朝着Jerry\texttt{Jerry}Jerry当前所在的位置跑去。由于Jerry\texttt{Jerry}Jerry也在移动Tom\texttt{Tom}Tom的路径看起来像一条曲线。在任意时刻Tom\texttt{Tom}Tom的位置都在Jerry\texttt{Jerry}Jerry的当前位置与圆心之间。Tom\texttt{Tom}Tom的速度也是恒定的V m/sV \, \text{m/s}Vm/s与Jerry\texttt{Jerry}Jerry的速度相同。求Tom\texttt{Tom}Tom需要多少秒才能抓住Jerry\texttt{Jerry}Jerry。输入格式输入第一行包含一个整数TTTT≤10000T \le 10000T≤10000表示测试用例的数量。接下来TTT行每行两个整数RRR和VVV满足0R,V≤100000 R, V \le 100000R,V≤10000。输出格式对于每个测试用例输出一行Case x: y其中xxx是测试用例编号从111开始yyy是Tom\texttt{Tom}Tom所需的时间。浮点数误差低于10−510^{-5}10−5将被忽略。样例输入4 45 100 5 1547 1000 10000 5668 5467输出Case 1: 0.70685835 Case 2: 0.00507691 Case 3: 0.15707963 Case 4: 1.62854830题目分析本题是一个经典的运动学追逐问题但Tom\texttt{Tom}Tom的追赶策略并非最优而是始终指向猎物当前位置即所谓“纯追踪”策略。猎物Jerry\texttt{Jerry}Jerry在半径为RRR的圆周上做匀速圆周运动追者Tom\texttt{Tom}Tom从圆心出发速度大小与猎物相同。我们需要求出追者恰好追上猎物的时间。由于两者速度大小相等且追者初始在圆心猎物在圆上直觉上追者似乎永远追不上因为猎物也在运动。但事实上由于追者始终指向猎物它的路径是一条螺旋线最终会在某个有限时刻与猎物相遇。本题难点在于推导该相遇时间。直接建立微分方程求解较为繁琐但可以通过对称性、极坐标变换或已知的物理结论简化。解题思路物理建模设圆心为原点OOO初始时Jerry\texttt{Jerry}Jerry位于圆上某点不妨取为(R,0)(R, 0)(R,0)其运动方向为逆时针角速度为ωV/R\omega V / RωV/R。Tom\texttt{Tom}Tom从原点出发速度大小也为VVV方向始终指向Jerry\texttt{Jerry}Jerry的瞬时位置。在任意时刻ttt设Jerry\texttt{Jerry}Jerry的极角为θ(t)ωt\theta(t) \omega tθ(t)ωt取初始θ(0)0\theta(0) 0θ(0)0Tom\texttt{Tom}Tom的极坐标为(r(t),ϕ(t))(r(t), \phi(t))(r(t),ϕ(t))。由于Tom\texttt{Tom}Tom始终指向Jerry\texttt{Jerry}Jerry其速度方向沿着两者连线即从Tom\texttt{Tom}Tom指向Jerry\texttt{Jerry}Jerry的方向。我们可以列出极坐标下的微分方程组径向速度r˙−Vcos⁡α\dot{r} -V \cos \alphar˙−Vcosα其中α\alphaα是连线方向与径向方向的夹角。横向速度rϕ˙Vsin⁡αr \dot{\phi} V \sin \alpharϕ˙​Vsinα。而α\alphaα与极角差δ(t)θ(t)−ϕ(t)\delta(t) \theta(t) - \phi(t)δ(t)θ(t)−ϕ(t)有关。通过几何关系可以得到tan⁡αRsin⁡δRcos⁡δ−r\tan \alpha \frac{R \sin \delta}{R \cos \delta - r}tanαRcosδ−rRsinδ​这里需要小心符号但基本关系成立。关键结论对于等速纯追踪问题存在一个优美结论当追者速度等于被追者速度时追者从圆心出发追上圆上运动目标所需的时间恰好是目标转过π2\frac{\pi}{2}2π​弧度所用的时间。即t弧长速度R⋅π2VπR2V. t \frac{\text{弧长}}{\text{速度}} \frac{R \cdot \frac{\pi}{2}}{V} \frac{\pi R}{2V}.t速度弧长​VR⋅2π​​2VπR​.这个结论可以通过变量替换或守恒量证明。例如设ur/Ru r / Rur/R并利用角度关系可以将微分方程化为dudθusin⁡θ−1−u2…\frac{du}{d\theta} \frac{u \sin \theta - \sqrt{1 - u^2}}{\dots}dθdu​…usinθ−1−u2​​等形式最终积分可得usin⁡θu \sin \thetausinθ当θ∈[0,π/2]\theta \in [0, \pi/2]θ∈[0,π/2]。当θπ/2\theta \pi/2θπ/2时u1u 1u1即rRr RrR此时追者恰好到达圆上且与猎物相会因为此时ϕθ\phi \thetaϕθ角度重合。因此相遇时间为θ/ω(π/2)/(V/R)πR/(2V)\theta / \omega (\pi/2) / (V/R) \pi R / (2V)θ/ω(π/2)/(V/R)πR/(2V)。算法步骤读入测试用例数TTT。对每个用例读入RRR和VVV。计算答案ansπ×R2×V\textit{ans} \frac{\pi \times R}{2 \times V}ans2×Vπ×R​。按格式输出保留足够多的小数位如 10 位。复杂度分析时间复杂度O(T)O(T)O(T)每个测试用例常数时间。空间复杂度O(1)O(1)O(1)仅需几个变量。代码实现// Jerrys Game// UVa ID: 13056// Verdict: Accepted// Submission Date: 2026-06-20// UVa Run Time: 0.000s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){intT;scanf(%d,T);constdoublepiacos(-1.0);for(intcaseNo1;caseNoT;caseNo){intR,V;scanf(%d %d,R,V);doubleans(pi/2.0)*(double)R/(double)V;printf(Case %d: %.10f\n,caseNo,ans);}return0;}总结本题主要考察数学建模与几何物理直觉。关键点在于识别出等速圆周追逐的几何特性并利用已知结论直接得出时间公式πR2V\frac{\pi R}{2V}2VπR​避免了复杂的微分方程求解。这种“从物理直觉到简单公式”的思维在算法竞赛中经常出现平时应多积累常见运动模型的结论。此外浮点数精度需要注意使用double\texttt{double}double并输出 10 位小数足以满足10−510^{-5}10−5的误差要求。代码实现非常简洁体现了“数学推导先行代码自然简单”的解题思路。