旋转卡壳学习笔记 | P1452 题解

王熙文 · 2023-10-27 11:33:37 · 题解

前言

洛谷题解区和 oi-wiki 都没有这个算法的证明，可能是证明太恶心了。因此我来写一个不严谨的证明。有一些结论可以直接从图形看出来，就不写证明了，因为这些的证明可能需要深入到凸包的定义等等，太麻烦了。

问题

P1452。

思路

• 结论 1：

凸包的直径为凸包上的点两两距离的最大值。

证明：首先凸包的直径一定在凸包的边上，否则将这条线段延长一定能交于边上。现在只需要考虑两点分别在两条边上的距离的最大值。根据勾股定理可知，一个点与一条边上的点的距离的最大值一定为这个点与边的端点的距离的最大值。考虑调整，对于两个点，可以先将一个点变成边的端点，再将另一个点变成边的端点，这样一定更优。所以两点分别在两条边上的距离的最大值为两条边的端点两两距离的最大值。

• 结论 2：

在凸包上所有点距离任意一条边的距离（垂线的长度）是单峰函数。

证明：可以想象将凸包旋转使得这条边与 x 轴重合，此时点的距离即为 y 坐标。如果存在三个点使得中间的点与边的距离最小，则第三个点一定是向外连出去的（如果向内就不可能再连到这条边了），而第三个点必须需要连回来，这样反复横跳的图形一定不是凸包。

下文称与一条边距离最大的点为这条边对应的点。

• 结论 3：

从一条边顺时针移动到相邻的那条边，则边对应的点要么不动要么顺时针移动。

证明：假设对于两条边，考虑第二条边对应的点在第一条边的对应的点的哪里。如下图，下面是两条边，上面两条直线的交点是第一条边对应的点，那么第二条边对应的点必须在阴影部分（在线段 1 下面且在线段 2 上面），所以移动方向不能为逆时针。

• 结论 4：

从一条边 l_1 顺时针移动到这条边的端点 A，若 A 和与这个点距离最大的点 B 是凸包的直径，则从 l_1 对应的点 C 到与 B 的移动方向也是顺时针。

证明：因为 A 是凸包的直径的一端，所以 B 一定在 l_1 的垂直平分线的逆时针移动方向侧（如果将这条边放到图的最下面，则逆时针移动方向侧即为右侧）。所以如果移动方向为逆时针，C 与 A 的距离就比 B 与 A 的距离大（首先 C 到 l_1 的垂线比 B 大，其次因为是逆时针移动且 B 在垂直平分线逆时针移动方向侧，C 的垂足到 A 的距离比 B 大），与定义矛盾。详见下图，下面横着的线为边，竖着的线为垂直平分线，点 1 为 C，点 2 为 B。如果移动方向为逆时针，则点 2 的距离一定不如点 1 大。

• 结论 5：

在点随机移动 eps 个距离后，凸包的直径为每条边的两个端点与这条边对应的点的距离的最大值。

因为下面的证明需要满足过一个点的两条边对应的点作对应边的平行线后两条平行线的交点不为凸包上的点（比如正六边形就不满足），所以需要将点随机移动 eps 个距离。原因详见下文。但是如果不随机移动点也有可能是正确的，只是我不会证明。

证明：对于一个直径的端点 A，考虑过包含它的两条边 l_1,l_2 的对应点 B,C 分别作 l_1,l_2 的平行线，设为 l_3,l_4。则根据对应点的定义凸包内的所有点都在 l_3,l_4 的下面。设与 A 距离最大的点为 D，根据结论 4，D 在凸包中的位置一定在 B,C 之间。如果 D 是 B 或 C，则已经找到了这条有可能是直径的线段 AD。否则，当 D 不为 l_3,l_4 的交点时，包含 D 的两条边中至少有一条边 l_5 的斜率在 l_3,l_4 之间且不与它们相等。那么 l_5 对应的点一定为 A。所以一定会得到 AD 这条线段。

已知了这 5 个结论，就可以证明旋转卡壳的正确性了。算法的流程是：遍历每条边，使用双指针找到每条边对应的点。并求出边的两个端点与这个点的距离。这个距离的最大值即为答案。

过程中需要求一个点与一条直线的距离。可以求出这个点与直线上任意两个点组成的三角形的面积，再乘 2 除以两个点的距离。

代码

#include<bits/stdc++.h>
using namespace std;
#define double long double
#define pdd pair<double,double>
double get_dis(pdd x,pdd y)
{
    return sqrt((x.first-y.first)*(x.first-y.first)+(x.second-y.second)*(x.second-y.second));
}
double check(pdd l1,pdd r1,pdd l2,pdd r2)
{
    return (r1.first-l1.first)*(r2.second-l2.second)-(r1.second-l1.second)*(r2.first-l2.first);
}
int n;
pdd a[100010];
bool cmp(pdd x,pdd y) { return check(a[1],x,a[1],y)>0; }
int tot; pdd st[100010];
double get_dis(pdd x,pdd y,pdd z)
{
    double a=get_dis(x,y),b=get_dis(x,z),c=get_dis(y,z);
    double p=(a+b+c)/2;
    return sqrt(p*(p-a)*(p-b)*(p-c))*2/a;
}
int main()
{
    cin>>n;
    double in=1e9; int wz;
    mt19937 rnd(time(0));
    for(int i=1; i<=n; ++i)
    {
        cin>>a[i].first>>a[i].second;
        a[i].first+=rnd()*1.0/1e15,a[i].second+=rnd()*1.0/1e15;
        if(in>a[i].second) in=a[i].second,wz=i;
    }
    swap(a[1],a[wz]);
    sort(a+2,a+n+1,cmp);
    st[tot=1]=a[1];
    for(int i=2; i<=n; ++i)
    {
        while(tot>=2 && check(st[tot-1],st[tot],st[tot],a[i])<0) --tot;
        st[++tot]=a[i];
    }
    for(int i=1; i<=tot; ++i) st[i+tot]=st[i];
    int now=2;
    double ans=0;
    for(int i=1; i<=tot; ++i)
    {
        while(get_dis(st[i],st[i+1],st[now])<get_dis(st[i],st[i+1],st[now+1])) ++now;
        ans=max(ans,max(get_dis(st[i],st[now]),get_dis(st[i+1],st[now])));
    }
    printf("%.0Lf",ans*ans);
    return 0;
}