如何计算拦截全部运动点后所有点返回原点的总耗时？

核心前提 #

拦截者速度大于所有目标点，因此可以自由选择拦截顺序，不存在无法到达的情况。我们要找的是能让所有目标点最快回到原点的拦截顺序及对应总时间。

单个目标点的时间逻辑 #

对任意目标点i：

• 初始位置(x_i, y_i)，速度v_i，方向单位向量(cos(a_i), sin(a_i))，所以t时刻位置为(x_i + v_i*t*cos(a_i), y_i + v_i*t*sin(a_i))。
• 假设拦截发生在全局时刻T_i，此时目标点位置为Q_i，那么它返回原点的时间是|Q_i|/v_i，所以该点回到原点的总时刻是T_i + |Q_i|/v_i。
• 拦截者到达Q_i的时刻就是T_i，这个时刻取决于拦截顺序——如果拦截者先去拦其他点，T_i会延后，导致该点的返回时刻也延后。

关键贪心策略 #

不同目标点的返回时刻对拦截延后的敏感度不同：定义k_i = 1 + V/v_i（V是拦截者速度），这个值越大，说明拦截时刻每延后1单位，该点的返回时刻就多延后k_i单位。优先拦截k_i大的点，能避免总时间被这类高敏感度的点拖长。

具体计算步骤 #

1. 预处理每个目标点

   • 计算单独拦截时的最早拦截时刻T_i0：解方程|(x_i + v_i*t*cos(a_i), y_i + v_i*t*sin(a_i))| = V*t，展开为二次方程(v_i² - V²)t² + 2*(x_i*cos(a_i)+y_i*sin(a_i))*v_i*t + (x_i²+y_i²) = 0，取正根得到T_i0。
   • 计算k_i = 1 + V/v_i。

2. 排序目标点
   按k_i从大到小排序，k_i越大的越先拦截。

3. 模拟拦截流程

   • 初始化：拦截者在原点，当前全局时间t=0。
   • 遍历排序后的每个点：
     • 计算当前时刻t时，目标点的位置P = (x_i + v_i*t*cos(a_i), y_i + v_i*t*sin(a_i))。
     • 计算拦截者从当前位置到拦截该点所需的时间delta_t：解方程|P - pos_interceptor + v_i*delta_t*(cos(a_i), sin(a_i))| = V*delta_t，取正根。
     • 更新全局时间t += delta_t，此时拦截点Q_i = (x_i + v_i*t*cos(a_i), y_i + v_i*t*sin(a_i))。
     • 记录该点返回原点的时刻t + |Q_i|/v_i。
     • 更新拦截者位置为Q_i。

4. 确定总时间
   所有点返回时刻中的最大值就是最终的总时间。

特殊情况处理 #

• 若目标点初始在原点：无需拦截，返回时刻为0。
• 若目标点初始运动方向指向原点：可立即拦截，返回时刻为|(x_i,y_i)|/v_i。

内容的提问来源于stack exchange，提问作者JohnD