旋轉卡殼簡介（POJ2187）（洛谷P1452）

讀音

word上是這麼讀的：

前置技能

凸包

算法用途

旋轉卡殼可以在 O(n) O ( n ) 的時間内确定一對對踵點對，它的用途包括但不限于：計算距離（凸多邊形直徑）、計算外接矩形（最小面積/周長）、三角剖分（洋蔥三角剖分）等其他奇奇怪怪的東西。

算法實作（模闆）

以POJ2187（洛谷P1452）為例。

這道題要我們求所有點之間的最大距離。我們先求出這些點的凸包，最大距離肯定在凸包的對踵點對上。那麼我們枚舉所有的對踵點對就好了，而旋轉卡殼就是實作這個的。

對于每個點，我們枚舉它的對踵點對。假設目前點的為 i i ，上一個點的對踵點對為xx，那麼當 (x+1→−x⃗ )×(i⃗ −x⃗ )≥(x+1→−x⃗ )×(i+1→−x⃗ ) ( x + 1 → − x → ) × ( i → − x → ) ≥ ( x + 1 → − x → ) × ( i + 1 → − x → ) 時，說明 x x 仍不是ii的對踵點對（因為 i+1 i + 1 比 i i 更符合）。那麼把x+1x+1并繼續驗證。當找到對踵點對時更新答案就好了。

代碼實作（旋轉卡殼為RC()）：

#include<cmath>
#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 50005
#define F friend
#define eps 1e-7
#define sqr(x) ((x)*(x))
#define abs(x) ((x)>0?(x):-(x))
using namespace std;
struct P{
    int x,y;
    F bool operator < (P a,P b){
        return abs(a.y-b.y)<eps?a.x<b.x:a.y<b.y;
    }
    F int cs(P a,P b,P c){//叉積
        return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
    }
    F int dis(P a,P b){
        return sqr(a.x-b.x)+sqr(a.y-b.y);
    }
}t[N],s[N];
int n,tp,ans;
inline char readc(){
    static char buf[],*l=buf,*r=buf;
    if (l==r) r=(l=buf)+fread(buf,,,stdin);
    if (l==r) return EOF; return *l++;
}
inline int _read(){
    int x=,f=; char ch=readc();
    while (!isdigit(ch)) { if (ch=='-') f=-; ch=readc(); }
    while (isdigit(ch)) x=(x<<)+(x<<)+(ch^),ch=readc();
    return x*f;
}
inline bool cmp(P a,P b){
    int f=cs(t[],a,b); if (f) return f>;
    return dis(t[],a)-dis(t[],b)<eps*eps;
}
inline void GR(){//凸包
    sort(t+,t+n+),s[++tp]=t[],sort(t+,t+n+,cmp);
    for (int i=;i<=n;s[++tp]=t[i++])
        while (tp>&&cs(s[tp-],s[tp],t[i])<eps) tp--;
}
inline void RC(){//旋轉卡殼
    s[]=s[tp]; int x=;
    for (int i=;i<tp;ans=max(ans,dis(s[i++],s[x])))
        while (cs(s[x],s[x+],s[i])-cs(s[x],s[x+],s[i+])>eps)
            x=(x+)%tp;
}
int main(){
    n=_read();
    for (int i=;i<=n;i++)
        t[i].x=_read(),t[i].y=_read();
    return GR(),RC(),printf("%d\n",ans),;
}