旋转卡壳

旋转卡壳

---

概述

寻找二维平面内距离最远的点，通过做垂线的方式可以证明，最远的点一定位于凸包上。所以先求凸包的轮廓，然后通过变换对锺点的来进行操作，用两条平行线来进行边界的取值，可以用当一条平行线经过凸包上两个点的时候来进行迭代更新，最远的距离应该是最高的点和直线上两个点的距离取最大，同时最远的点是一个类似于爬山法的先增后减的，所以我们可以用双指针的做法来进行操作，时间复杂度为O(n)。

---

模板

给定一个二维平面，平面上有 N 个点。

每个点的位置可由一对整数坐标 (x,y) 来表示，不同的点位置不同。

请你求出平面上距离最远的点对之间的距离是多少。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N = 50010;
int n;
PII q[N];
int stk[N],top;
bool used[N];
PII operator - (PII a,PII b)
{
    return {a.x-b.x,a.y-b.y};
}
int cross(PII a,PII b)
{
    return a.x*b.y-a.y*b.x;
}
int area(PII a,PII b,PII c)
{
    return cross(b-a,c-a);
}
int get_dist(PII a,PII b)
{
    int dx=a.x-b.x;
    int dy=a.y-b.y;
    return dx*dx+dy*dy;
}
void get_convex()
{
    sort(q,q+n);
    for(int i=0;i<n;i++)
    {
        while(top>=2&&area(q[stk[top-2]],q[stk[top-1]],q[i])<=0)
        {
            if (area(q[stk[top-2]],q[stk[top-1]],q[i])<0)
                used[stk[--top]] = false;
            else top--;
        }
        stk[top++]=i;
        used[i]=true;
    }
    used[0]=false;
    for(int i=n-1;i>=0;i--)
    {
        if(used[i]) continue;
        while(top>=2&&area(q[stk[top-2]],q[stk[top-1]],q[i])<=0)    top--;
        stk[top++]=i;
    }
    top--;
}
int rotating_calipers()
{
    if(top<=2)  return get_dist(q[0],q[n-1]);
    int res=0;
    for(int i=0,j=2;i<top;i++)
    {
        auto d=q[stk[i]],e=q[stk[i+1]];
        while(area(d,e,q[stk[j]])<area(d,e,q[stk[j+1]]))    j=(j+1)%top;
        res=max(res,max(get_dist(d,q[stk[j]]),get_dist(e,q[stk[j]])));
    }
    return res;
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)    scanf("%d%d",&q[i].x,&q[i].y);
    get_convex();
    printf("%d\n",rotating_calipers());
    return 0;
}

---

矩阵覆盖

通过证明可得矩阵的一边一定位于凸包的一边上，因此我们在旋转卡壳的时候通过另外的两条垂直的平行线来进行判断长度，用高乘宽来进行迭代。

void rotating_calipers()
{
    for(int i=0,a=2,b=1,c=2;i<top;i++)
    {
        auto d=q[stk[i]],e=q[stk[i+1]];
        while(dcmp(area(d,e,q[stk[a]]),area(d,e,q[stk[a+1]]))<0)   a=(a+1)%top;
        while(dcmp(project(d,e,q[stk[b]]),project(d,e,q[stk[b+1]]))<0)  b=(b+1)%top;
        if(!i)  c=a;
        while(dcmp(project(d,e,q[stk[c]]),project(d,e,q[stk[c+1]]))>0)  c=(c+1)%top;
        auto x=q[stk[a]],y=q[stk[b]],z=q[stk[c]];
        double h=area(d,e,x)/get_len(e-d);
        double w=point(y-z,e-d)/get_len(e-d);
        if(h*w<min_area)
        {
            min_area=h*w;
            ans[0]=d+norm(e-d)*project(d,e,y);
            ans[3]=d+norm(e-d)*project(d,e,z);
            auto u=norm(rotate(e-d,-PI/2));
            ans[1]=ans[0]+u*h;
            ans[2]=ans[3]+u*h;
        }
    }
}

---