自动搬运

查看原文

来自洛谷，原作者为

	chen_zhe Aya 敲可爱的~

搬运于2025-08-24 22:52:07，当前版本为作者最后更新于2023-11-05 21:43:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

以下内容转载自官方题解：

假设已经找到了答案的 $a$ 和 $b$ 两个点，我们可以尝试沿着原有路径移动点 $a$。因为 $a$ 和 $b$ 是最优解，两个移动的方向都要（使得答案变差或者使得 $a$ 到 $b$ 的线段不合法）。如果有一个方向移动答案不变差且不会变得不合法，那就可以一直沿着那个方向移动，直到答案会变差或者马上会不合法。这两种情况都意味着 $a$ 到 $b$ 的线段碰到了原有折线的某个拐点。所以答案的 $ab$ 线段上一定要有一个原来的拐点。

有一个拐点以后，要么以它为中心旋转 $ab$ 连线到一个极小值点（把以拐点为视点看到的线段极角排序，分段三分），要么有两个拐点（枚举这两个点，连线，找到这条直线和原来折线的交点，处理这些交点之间抄近路的答案。抄近路要求不能穿过原来的折线，也不能碰到原来的折线。但是有些碰到的情况可以通过左右微调解决）。