题目描述考虑一个用绳子挂在墙壁钩子上的摆锤。当被推动时这个摆锤会来回摆动。现在想象在摆锤绳子的路径上放置其他钩子。摆锤会绕过它们甚至可能围绕它们打转。一般来说它会遵循比之前复杂得多的路径。一段时间后摆锤的运动将重复摆锤将进入一个周期性轨道。需要计算摆锤完成一个周期所经过的距离。更正式地说我们在墙上放置一个笛卡尔坐标系。摆锤的绳子固定在原点(0,0)(0,0)(0,0)。xxx轴指向右yyy轴指向上。摆锤的绳子长度为rrr。摆锤从(−r,0)(-r, 0)(−r,0)位置释放开始向右摆动。此外平面上还有nnn个额外的钩子可能影响摆锤的路径。理想假设钩子和绳子的直径为零摆锤没有能量损失如摩擦摆锤永远不会碰到钩子只有绳子会碰到绳子由某种未来材料制成只在接触钩子处弯曲其他地方保持刚性由于重力作用摆锤永远不会达到高于起始点的高度即永远不会高于xxx轴。它要么再次达到初始高度要么无限地绕钩子旋转。输入格式输入文件包含多个测试用例。每个测试用例以一行包含整数nnn钩子数量1≤n5001 \leq n 5001≤n500和实数rrr摆绳长度开始。接下来的nnn行每行包含两个整数表示对应钩子的xxx和yyy坐标。文件以r0r 0r0的用例结束该用例不处理。输出格式对于每个用例输出一行Pendulum #1、Pendulum #2等。然后输出一行包含摆锤完成一个周期所经过的距离不计算到达轨道起点所经过的距离精确到小数点后两位。每个测试用例后输出一个空行。样例输入2 16.0 3 -4 -3 -4 1 18.0 5 -12 0 0样例输出Pendulum #1 Length of periodic orbit 87.66 Pendulum #2 Length of periodic orbit 31.42题目分析问题的本质这是一个几何模拟问题。摆锤从左侧水平位置释放在重力作用下向右摆动。绳子在遇到钩子时会弯曲绳子的一部分会“缠绕”在钩子上从而改变有效摆长。关键物理原理摆锤的势能守恒因此它永远不会超过初始高度y0y 0y0绳子总是拉紧的当绳子碰到钩子时钩子到摆锤之间的绳子保持直线而钩子到悬挂点之间的绳子则“绕过”钩子运动过程摆锤从(−r,0)(-r, 0)(−r,0)释放。在重力作用下它向右下方运动然后向上摆动。由于能量守恒它将在yyy轴上的某个最高点停止但不会超过y0y 0y0。如果过程中没有碰到任何钩子它会在初始高度处停止然后反向摆回形成一个完整的周期。当绳子碰到钩子时钩子成为新的“支点”。此时有效摆长变为从钩子到摆锤的距离。摆锤继续摆动可能会碰到更多钩子。轨道类型最终摆锤会进入两种可能的周期性轨道左右摆动在xxx轴两侧来回摆动最高点为y0y 0y0绕圈完全围绕一个钩子旋转类似于圆周运动模拟方法由于钩子数量有限摆锤的绳子每次只会缠绕在最“外侧”的钩子上。我们可以模拟摆锤的运动每一步确定下一个被绳子接触的钩子然后更新有效摆长和角度范围直到进入周期性状态。解题思路步骤一坐标系与初始条件悬挂点主钩子(0,0)(0,0)(0,0)初始位置(−r,0)(-r, 0)(−r,0)初始角度θ−π\theta -\piθ−π从负xxx轴方向开始步骤二钩子筛选只有满足以下条件的钩子才可能被绳子碰到钩子在xxx轴下方或xxx轴上y≤0y \le 0y≤0因为摆锤永远不会高于xxx轴钩子到当前悬挂点的距离 ≤ 当前有效摆长步骤三确定下一个钩子在当前位置绳子从当前悬挂点OOO延伸到摆锤PPP。当摆锤摆动时绳子会扫过一定的角度范围。下一个被绳子接触的钩子是在这个角度范围内最靠近绳子的那个。具体来说对于每个候选钩子HHH计算极角θHatan2(Hy−Oy,Hx−Ox)\theta_H \text{atan2}(H_y - O_y, H_x - O_x)θH​atan2(Hy​−Oy​,Hx​−Ox​)这个角度必须在当前扫过的角度范围内从上次角度到本次角度选择使绳子偏转最大的钩子即角度变化最小的方向实际上是选择最“靠右”的钩子步骤四更新状态当绳子碰到钩子HHH时从OOO到HHH的一段绳子被“固定”在钩子上新的悬挂点变为HHH新的有效摆长变为原摆长减去∣OH∣|OH|∣OH∣新的角度为从HHH到PPP的方向角摆锤继续摆动步骤五终止条件模拟终止条件如果当前摆长大于或等于悬挂点到xxx轴的距离摆锤可以到达xxx轴。此时它会在xxx轴上反弹形成左右摆动周期。轨道长度 2×2 \times2×从当前角度到xxx轴的弧长如果当前摆长小于悬挂点到xxx轴的距离摆锤无法到达xxx轴它会绕悬挂点做圆周运动。轨道长度 2π×2\pi \times2π×摆长步骤六轨道长度计算在模拟过程中累加每次摆锤摆过的弧长弧长摆长×∣Δθ∣弧长 摆长 \times |\Delta\theta|弧长摆长×∣Δθ∣。当到达xxx轴或进入圆周运动时加上最后一段弧长然后乘以222因为左右摆动对称得到完整周期的长度。算法复杂度分析时间复杂度最多有nnn个钩子每一步确定下一个钩子O(n)O(n)O(n)最多O(n)O(n)O(n)步每个钩子最多被缠绕一次总复杂度O(n2)O(n^2)O(n2)n500n 500n500完全可行空间复杂度存储钩子坐标O(n)O(n)O(n)总空间复杂度O(n)O(n)O(n)正确性证明引理 1摆锤的运动由绳子与钩子的接触点决定。每次接触后绳子被“缩短”摆锤绕新支点摆动。证明绳子总是拉紧的当碰到钩子时钩子成为新的支点。由于绳子不会打滑钩子到摆锤之间的部分保持直线。□\square□引理 2在摆锤摆动过程中绳子每次只会碰到最“外侧”的钩子即最靠近当前绳子方向的钩子。证明如果存在多个可能的钩子最外侧的钩子会首先被绳子碰到。□\square□引理 3模拟会在有限步内终止因为每次有效摆长严格减小且钩子数量有限。证明每次缠绕都会使有效摆长减小减去∣OH∣0|OH| 0∣OH∣0因此最多进行nnn步。□\square□引理 4最终轨道要么是左右摆动到达xxx轴要么是圆周运动无法到达xxx轴。证明能量守恒决定了摆锤无法超过初始高度。如果有效摆长足够长它可以回到y0y 0y0否则它会在最低点以下摆动形成圆周运动。□\square□参考代码// Pendulum// UVa ID: 319// Verdict: Accepted// Submission Date: 2017-05-29// UVa Run Time: 0.000s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constdoubleEPSILON1e-7,PI2.0*acos(0.0);structpoint{doublex,y;};// 计算两点间距离doublegetDist(constpointp1,constpointp2){returnsqrt(pow(p1.x-p2.x,2)pow(p1.y-p2.y,2));}// 叉积计算向量 ab 和 ac 的叉积doublecp(constpointa,constpointb,constpointc){return(b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);}intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intn,cases0;doublex1,y1,lengthOfString;while(cinnlengthOfString,lengthOfString0.0){coutPendulum #cases\n;// 钩子列表原点主钩子始终在列表中vectorpointhooks;hooks.push_back(point{0.0,0.0});for(inti0;in;i){cinx1y1;// 忽略 y 0 的钩子摆锤无法到达if(y10)continue;// 忽略距离超过摆长的钩子if(lengthOfStringEPSILONsqrt(x1*x1y1*y1))continue;hooks.push_back(point{x1,y1});}intlastHookIdx0;// 当前悬挂点索引doublelastTheta-PI;// 当前角度从负 x 轴开始doubleorbit0.0;// 轨道长度while(true){intnextHookIdx-1;// 当前摆长下摆锤能到达的最右角度与 x 轴交点doublerightmostAngleasin(fabs(hooks[lastHookIdx].y)/lengthOfString);// 寻找下一个被绳子碰到的钩子for(inti0;ihooks.size();i){if(ilastHookIdx)continue;doublecurrentDistgetDist(hooks[i],hooks[lastHookIdx]);if(lengthOfStringEPSILONcurrentDist)continue;doublethetaatan2(hooks[i].y-hooks[lastHookIdx].y,hooks[i].x-hooks[lastHookIdx].x);// 检查角度是否在当前摆动范围内if(theta-rightmostAngleEPSILON||thetaEPSILONlastTheta){if(fabs(hooks[lastHookIdx].y)lengthOfStringEPSILON)continue;}// 选择最合适的钩子使绳子偏转最大的if(nextHookIdx-1){nextHookIdxi;}else{doubleCPcp(hooks[lastHookIdx],hooks[nextHookIdx],hooks[i]);if(fabs(CP)EPSILON){// 共线时选择距离更近的doublelastDistgetDist(hooks[nextHookIdx],hooks[lastHookIdx]);if(lastDistEPSILONcurrentDist)nextHookIdxi;}elseif(CP0){nextHookIdxi;}}}// 没有更多钩子进入周期性轨道if(nextHookIdx-1){if(lengthOfStringfabs(hooks[lastHookIdx].y)EPSILON){// 无法到达 x 轴做圆周运动orbit2.0*PI*lengthOfString;}else{// 左右摆动orbitlengthOfString*(rightmostAngle-lastTheta);orbit*2.0;}coutLength of periodic orbit ;coutfixedsetprecision(2)orbit\n\n;break;}// 累加弧长更新状态doublenextThetaatan2(hooks[nextHookIdx].y-hooks[lastHookIdx].y,hooks[nextHookIdx].x-hooks[lastHookIdx].x);orbitlengthOfString*fabs(nextTheta-lastTheta);lengthOfString-getDist(hooks[nextHookIdx],hooks[lastHookIdx]);lastHookIdxnextHookIdx;lastThetanextTheta;}}return0;}总结本题的核心在于几何模拟每次找到下一个被绳子接触的钩子状态更新改变悬挂点和有效摆长终止条件根据是否到达xxx轴区分两种轨道类型关键点回顾知识点说明悬挂点原点为主钩子初始角度−π-\pi−π从负xxx轴钩子筛选y≤0y \le 0y≤0距离 ≤ 摆长下一个钩子使绳子偏转最大的钩子弧长计算$l \times轨道类型左右摆动 或 圆周运动物理直觉摆锤的运动路径是所有可能路径中能量最小的那条。绳子的弯曲发生在钩子处而钩子的选择由几何约束决定。这种模拟方法虽然简单但正确反映了系统的动力学行为。