题解：P12130 [蓝桥杯 2025 省 B] 移动距离
brofea5
·
·
题解
题意
一个点有两种移动方式，沿着 x 轴正方向移动、以原点为圆心旋转，问走到点 (233,666) 需要经过的路程
答案四舍五入至整数
思路
答案很简单，计算原点到 (233,666) 的距离 r=\sqrt{233^2+666^2}，沿着 +x 移动 r，再旋转至终点
旋转的角度 \theta=\arcsin(666/r)
最终的路程就是：（四舍五入至整数）
S=r+\frac\alpha{2\pi}\cdot 2\pi r=r(1+\arcsin(666/r))\approx 1576
如果忘记 C++ 有 asin() 函数（\arcsin 函数）了怎么办呢？
- 用
sin() 函数数值逼近，可以从 0.0000001 循环到 3.1400000，也可以用二分
- 在终端里用 python 的
math.asin() 函数
- 用 Excel 的 ASIN() 函数，如果不记得函数名可以在“告诉我”中搜索“函数”并寻找反函数
- 泰勒展开
要证明这个走法就是最佳的其实还挺麻烦，不过在几何上就比较好理解，假设有这么一条路径 r_1,c_1,r_2,c_2,r_3,c_3
把所有圆弧平移到右侧首尾相连，把所有线段平移到 x 轴上，可以看出线段一定长于原本的 r，圆弧和一定长于原本的 c （可以用三角不等式证明）
严谨来说，应该用微积分证明，我们将每一次移动都看作是微小的坐标变化(\delta x_i,\delta y_i)
对于点 (x,y) ，旋转微小角 d\theta 的距离变化为 r=x^2+y^2，旋转，则路程为 \delta L_R=r\,d\theta，对于沿 x 轴平移，路程为 \delta L_T=\delta x，此时 \theta=\arctan(y/x)，随着 x 增大而增大
$$
\sum_{i\in T} \delta x_i +\sum_{j\in R} (-y_j\,d\theta_j) \;=\;233 ,\sum_{j\in R} x_j\,d\theta_j\;=\;666
$$
综上可以构造拉格朗日函数：
$$
\mathcal{L}=\sum_{i\in T} \delta x_i+\sum_{j\in R} r_j\,d\theta_j
+\lambda\Biggl( \sum_{i\in T} \delta x_i +\sum_{j\in R} (-y_j\,d\theta_j)-233\Biggr)
+\mu\Biggl(\sum_{j\in R} x_j\,d\theta_j-666\Biggr)\,,
$$
对 $\delta x_i$ 求偏导数，可以求出 $\lambda=-1$，然后考虑旋转的部分，可以设
$$
f_j = r_j\,d\theta_j -\lambda\,y_j\,d\theta_j+\mu\,x_j\,d\theta_j=d\theta_j\Bigl(r_j + y_j+\mu\,x_j\Bigr)\,.
$$
求偏导后可知，每个旋转操作要满足：
$$
\frac{\partial f_j}{\partial (d\theta_j)}=r_j + y_j+\mu\,x_j=0\tag1
$$
注意到每次旋转都是绕原点进行，$x_j,y_j$ 由之前的运动决定，而又要使得在每个旋转的贡献中使得 $\mu$ 保持一致，则各个旋转都必须满足上式
考虑理想的候选方案，设目标点为 $(r_f,\theta_f)$ 若先水平平移至 $(r_f,0)$，则对于所有在这点的旋转操作都有
$$
r_j + y_j+\mu\,x_j=r_f+0-1\times r_f=0
$$
正好满足（1）且每个旋转必要条件一致
若在平移未完成前旋转，即 $x<r_f$ 或 $y\ne0$。将（1）写为：
$$
\sqrt{x_j^2+y_j^2}+y_j+\mu\,x_j=0
$$
若在平移还未完成时就引入旋转，那么（1）要求的 $\mu$ 会因不同步而不可能一致地取一个常数，而会取一个更“严格”的值，使得后续整体代价增大，也就是说无法找到一个 $\mu$ 满足所有旋转步都不发生效率损失
在这道题中，$\mu$ 恒定事实上使得 $\theta$ 为一个差为 $0$ 的等差旋转角，也就是说，每次都旋转 $\theta_j$ 走到终点的路径就是最短的，对于任何终点都成立，这点在几何上不难证明
走多少次都是一样的，那就走一次吧
AC 代码：
```cpp
#include <bits/stdc++.h>
int main() {
double r = sqrt(233 * 233 + 666 * 666);
int res = r + asin(666.0 / r) * r;
std::cout << res;
}
```