旋转卡壳

前言

旋转卡壳的模板及用法。

算法讲解

先来了解一下旋转卡壳算法：

旋转卡壳（Rotating Calipers，也称 旋转卡尺）算法，在凸包算法的基础上，通过枚举凸包上某一条边的同时维护其他需要的点，能够在线性时间内求解如凸包直径、最小矩形覆盖等和凸包性质相关的问题。——某个靠谱的 wiki

凸包直径，或着说多边形直径，也可理解成边上任意两点间的距离的最大值。
那么对于一个平面上的一个点集，求解任意两点间距离最大值，最朴素最暴力的办法就是枚举两个点，但是时间复杂度为 $O(n^2)$，不可接受。
那么这里就有一个 $O(n)$ 的妙妙做法：旋转卡壳，因计算时像一对平行线卡住凸包旋转得名。

定义如果过凸包上的两个点可以画一对平行直线，使凸包上的所有点都夹在两条平行线之间或落在平行线上，那么这两个点叫做一对对踵点。
那么可知直径是由多边形的平行切线的最远距离决定。那么我们查询对踵点，找到距离最远的那一对即可。
在卡壳旋转的过程中，会出现夹住点和点、点和线（由上图可知，对踵点只有在平行线与凸包某一边平行的时候才会发生变化，那我们就可以找到它变化的时候，去查询对踵点）、线和线，但是我们只用考虑点和线的情况即可。这里其实有一个非常好的性质：随着我们不断按照凸包的顺序逆时针遍历凸包上的点，可知点与定点之间的距离不满足单调性，但是点到定直线的距离满足单调性，所以考虑点和线的情况可以保证正确性与时间复杂度。
一个对踵点到对应边的距离既然是最大的，那我们在确定了一条边时就可以遍历找到它的对应对踵点。这个时候点到直线的距离随着遍历应该是一个单峰函数。那我们找到逆时针的下一个点，如果下一个点到该边的距离比当前点更优，那就跳到下一个点；否则当前点就是该边的对踵点。
判定点到直线距离可以用叉积，遍历复杂度为 $O(n)$，而可以证明，寻找对踵点的复杂度均摊也是 $O(n)$，中途记录对踵点到边的两个顶点的最大距离即可。遍历完即可得到答案。
下面放一下 洛谷旋转卡壳模板

Code

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<set>
##define put putchar
##define ls(a) (a << 1)
##define rs(a) (a << 1 | 1)
##define pii pair<int, int>

using namespace std;

const int N = 1e5 + 10;
const double eps = 1e-6;
const double pi = acos(-1);

int n, cnt = 0;
double ans = 0;

struct point {
    double x, y;
    point (const double& x0 = 0, const double& y0 = 0) : x(x0), y(y0) { }
    point operator + (const point& t)  const {
        return point(x + t.x, y + t.y);
    }
    point operator - (const point& t)  const {
        return point(x - t.x, y - t.y);
    }
    point operator * (const double& t)  const {
        return point(x * t, y * t);
    }
    point operator / (const double& t) const {
        return point(x / t, y / t);
    }
    point rotate() {
        return point(y, -x);
    }
} p[N], q[N];

double dot(const point& a, const point& b) {
    return a.x * b.x + a.y * b.y;
}
double cross(const point& a, const point& b) {
    return a.x * b.y - a.y * b.x;
}
double len(const point& a) {
    return sqrt(dot(a, a));
}
double dis(const point &a, const point &b) {
    return sqrt(dot(a - b, a - b));
}

template<class T>
inline void read(T &x) {
    T res = 0, f = 1; char cc = getchar();
    while(! isdigit(cc)) {
        if(cc == '-') f = -1;
        cc = getchar();
    }
    while(isdigit(cc)) res = (res << 1) + (res << 3) + cc - 48, cc = getchar();
    x = res * f; return ;
}
template<class T, class ...T1>
inline void read(T &x, T1 &...x1) {
    read(x), read(x1...); return ;
}
template<class T>
inline void write(T x) {
    if(x < 0) x = -x, put('-');
    if(x > 9) write(x / 10);
    put(x % 10 + 48); return ;
}
template<>
inline void write(char x) {
    put(x); return ;
}
template<class T, class ...T1>
inline void write(T x, T1 ...x1) {
    write(x),write(x1...); return ;
}
template <class T>
inline bool chkmax(T &x, T y) {
    return x < y ? x = y , 1 : 0;
}

int sign(double a)
{
    if(fabs(a) < eps)
        return 0;
    return a > 0 ? 1 : -1;
}

bool cmp(point a, point b) {
    if(sign(cross(a - p[1], b - p[1])) > 0)
        return true;
    if(sign(cross(a - p[1], b - p[1])) == 0 && sign(dis(p[1], a) - dis(p[1], b)) < 0)
        return true;
    return false;
}
bool check(point a, point b, point c) {
    return sign(cross(b - a, c - b)) <= 0;
}

void get_conv()
{
    int t = 1;
    for(int i = 2; i <= n; ++ i)
        if(sign(p[i].y - p[t].y) < 0 || (sign(p[i].y - p[t].y) == 0 && sign(p[i].x - p[t].x) < 0))
            t = i;
    swap(p[t], p[1]);
    sort(p + 2, p + n + 1, cmp);
    q[++ cnt] = p[1];
    for(int i = 2; i <= n; ++ i)
    {
        while(cnt > 1 && check(q[cnt - 1], q[cnt], p[i]))
            -- cnt;
        q[++ cnt] = p[i];
    }
    q[cnt + 1] = q[1];
    return ;
}

signed main()
{
   // freopen(".in", "r", stdin);
   // freopen(".out", "w", stdout);
    read(n);
    for(int i = 1; i <= n; ++ i)
        scanf("%lf%lf", &p[i].x, &p[i].y);
    get_conv();
    for(int i = 1, j = 2; i <= cnt; ++ i)
    {
        while(sign(cross(q[j] - q[i], q[j] - q[i + 1]) - cross(q[j + 1] - q[i], q[j + 1] - q[i + 1])) < 0)
            j = j % cnt + 1;
        ans = max(ans, max(dot(q[i] - q[j], q[i] - q[j]), dot(q[i + 1] - q[j], q[i + 1] - q[j])));
    }
    write((int) ans);
    return 0;
}

例题

P1452 [USACO03FALL] Beauty Contest G /【模板】旋转卡壳

模板题，代码附在上面。

P4166 [SCOI2007] 最大土地面积

links，一个小应用。
有一个很好的性质：如果凸包有至少四个点，那么组成最大四边形的四个点一定在凸包上。分情况讨论：

凸包大小小于等于 $2$ 时

可知原本所有的点都共线，那么答案为 $0$。

凸包大小为 $3$ 时

那么所有的点都在一个三角形内部，最后的四边形只能为一个凹四边形。
那么我们枚举所有点，那么这种情况下的四边形面积为凸包三角形的面积减去该点与凸包其中一条边构成的小三角形面积（三条边都要考虑一遍），在所有答案中取最大值。

凸包大小大于等于 $4$ 时

根据上文提到的性质（自己证一证吧），四边形四个点都在凸包上。
枚举四边形的对角线，那么在分别对另一条对角线的两个点（分居枚举的对角线两侧）跳指针，找到距离最远的那个点，最后的面积就是对角线长度乘上面的那个点到对角线的距离与下面的点的距离的和，取最大值即可，复杂度 $O(n^2)$。

Code

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<set>
##define put putchar
##define ls(a) (a << 1)
##define rs(a) (a << 1 | 1)
##define pii pair<int, int>

using namespace std;

const int N = 2e3 + 10;
const double eps = 1e-9;
const int INF = 1e9 + 7;

int n;
int cnt = 0;
double sum = 0.0;

struct point {
    double x, y;
    point (const double& x0 = 0, const double& y0 = 0) : x(x0), y(y0) { }
    point operator + (const point& t)  const {
        return point(x + t.x, y + t.y);
    }
    point operator - (const point& t)  const {
        return point(x - t.x, y - t.y);
    }
    point operator * (const double& t)  const {
        return point(x * t, y * t);
    }
    point operator / (const double& t) const {
        return point(x / t, y / t);
    }
    point rotate() {
        return point(y, -x);
    }
} p[N], low, q[N];

double dot(const point& a, const point& b) {
    return a.x * b.x + a.y * b.y;
}
double cross(const point& a, const point& b) {
    return a.x * b.y - a.y * b.x;
}
double len(const point& a) {
    return sqrt(dot(a, a));
}
double dis(const point &a, const point &b) {
    return sqrt(dot(a - b, a - b));
}

template<class T>
inline void read(T &x) {
    T res = 0, f = 1; char cc = getchar();
    while(! isdigit(cc)) {
        if(cc == '-') f = -1;
        cc = getchar();
    }
    while(isdigit(cc)) res = (res << 1) + (res << 3) + cc - 48, cc = getchar();
    x = res * f; return ;
}
template<class T, class ...T1>
inline void read(T &x, T1 &...x1) {
    read(x), read(x1...); return ;
}
template<class T>
inline void write(T x) {
    if(x < 0) x = -x, put('-');
    if(x > 9) write(x / 10);
    put(x % 10 + 48); return ;
}
template<>
inline void write(char x) {
    put(x); return ;
}
template<class T, class ...T1>
inline void write(T x, T1 ...x1) {
    write(x),write(x1...); return ;
}
template <class T>
inline bool chkmax(T &x, T y) {
    return x < y ? x = y , 1 : 0;
}

int sign(double a)
{
    if(fabs(a) < eps)
        return 0;
    return a > 0 ? 1 : -1;
}

bool cmp(point a, point b) {
    if(sign(cross(a - low, b - low)) > 0)
        return true;
    if(sign(cross(a - low, b - low)) == 0 && sign(dis(low, a) - dis(low, b)) < 0)
        return true;
    return false;
}
bool check(point a, point b, point c) {
    return sign(cross(b - a, c - b)) <= 0;
}
bool chks(point a, point b, point c, point d)
{
    return sign(fabs(cross(b - a, c - a)) - fabs(cross(b - a, d - a))) < 0;
}

double get_ans()
{
    if(cnt <= 2)
        return 0.0;
    if(cnt == 3)
    {
        double sum = cross(q[2] - q[1], q[3] - q[1]);
        double Min = INF;
        for(int i = 1; i <= n; ++ i)
            if(sign(p[i].x - q[1].x) && sign(p[i].x - q[2].x) && sign(p[i].x - q[3].x))
                Min = min(Min, cross(p[i] - q[2], p[i] - q[3])),
                min(cross(p[i] - q[1], p[i] - q[2]), cross(p[i] - q[3], p[i] - q[1]));
        if(Min == INF)
            return 0.0;
        return (sum - Min) / 2;
    }
    double res = -INF;
    for(int i = 1; i <= cnt; ++ i)
    {
        int x = i % cnt + 1, y = x % cnt + 1;
        for(int j = y; j != i; j = j % cnt + 1)
        {
            while(x != j && chks(q[i], q[j], q[x], q[x + 1])) x = x % cnt + 1;
            while(y != i && chks(q[i], q[j], q[y], q[y + 1])) y = y % cnt + 1;
            res = max(res, fabs(cross(q[j] - q[i], q[x] - q[i]))
            + fabs(cross(q[j] - q[i], q[y] - q[i])));
        }
    }
    return res / 2;
}

signed main()
{
   // freopen(".in", "r", stdin);
   // freopen(".out", "w", stdout);
    read(n), low.y = 1e6;
    for(int i = 1; i <= n; ++ i)
        scanf("%lf%lf", &p[i].x, &p[i].y),
        low = (sign(p[i].y - low.y) < 0 || (sign(p[i].y - low.y) == 0 && sign(p[i].x - low.x) < 0)) ? p[i] : low;
    sort(p + 1, p + n + 1, cmp);
    q[++ cnt] = low;
    for(int i = 1; i <= n; ++ i)
    {
        if(sign(p[i].x - low.x) == 0 && sign(p[i].y - low.y) == 0)
            continue;
        while(cnt > 1 && check(q[cnt - 1], q[cnt], p[i]))
            -- cnt;
        q[++ cnt] = p[i];
    }
    q[cnt + 1] = q[1];
    printf("%.3lf", get_ans());
    return 0;
}

P3187 [HNOI2007] 最小矩形覆盖

links，也比较典。
性质：最后得到的矩形每条边必定经过凸包的顶点（或者和凸包的一条边重合），可自己证明。
那么根据旋转卡壳调整法，可知在矩形与凸包的一条边重合时更优。
那么枚举边。考虑三个点（该边所对应的）：

1. 最上点，直接用旋转卡壳叉积求面积即可。
2. 最右点，用点积判断就行了。
3. 最左点，跟最右点几乎一样，只是旋转方向相反。

那么根据这三个点，做出平行线与垂直线，求交即可的到矩形的顶点。（这个题有点卡精度）

Code

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<set>
#include<map>
##define put putchar
##define ls(a) (a << 1)
##define rs(a) (a << 1 | 1)
##define pii pair<int, int>

using namespace std;

const int N = 5e4 + 10;
const double eps = 1e-10;

int n, cnt = 0;
double S = 1e6;

int sign(double a) {
    if(fabs(a) < eps)
        return 0;
    return a > 0 ? 1 : -1;
}
struct point {
    double x, y;
    point (const double& x0 = 0, const double& y0 = 0) : x(x0), y(y0) { }
    point operator + (const point& t)  const {
        return point(x + t.x, y + t.y);
    }
    point operator - (const point& t)  const {
        return point(x - t.x, y - t.y);
    }
    point operator * (const double& t)  const {
        return point(x * t, y * t);
    }
    point operator / (const double& t) const {
        return point(x / t, y / t);
    }
    point rotate() {
        return point(y, -x);
    }
} p[N], low, q[N], ans[5];

double dot(const point& a, const point& b) {
    return a.x * b.x + a.y * b.y;
}
double cross(const point& a, const point& b) {
    return a.x * b.y - a.y * b.x;
}
double len(const point& a) {
    return sqrt(dot(a, a));
}
double dis(const point &a, const point &b) {
    return sqrt(dot(a - b, a - b));
}

struct line {
    point a, b; double ang;
    line() {}
    line(point A, point B){
        a = A, b = B;
        ang = atan2((b - a).y, (b - a).x);
    }
    
    bool operator < (const line& t) const {
      if(sign(ang - t.ang) == 0)
          return sign(cross(t.a - a, t.b - a)) == 1;
      return ang < t.ang;
    }
} ;

template<class T>
inline void read(T &x) {
    T res = 0, f = 1; char cc = getchar();
    while(! isdigit(cc)) {
        if(cc == '-') f = -1;
        cc = getchar();
    }
    while(isdigit(cc)) res = (res << 1) + (res << 3) + cc - 48, cc = getchar();
    x = res * f; return ;
}
template<class T, class ...T1>
inline void read(T &x, T1 &...x1) {
    read(x), read(x1...); return ;
}
template<class T>
inline void write(T x) {
    if(x < 0) x = -x, put('-');
    if(x > 9) write(x / 10);
    put(x % 10 + 48); return ;
}
template<>
inline void write(char x) {
    put(x); return ;
}
template<class T, class ...T1>
inline void write(T x, T1 ...x1) {
    write(x),write(x1...); return ;
}
template <class T>
inline bool chkmax(T &x, T y) {
    return x < y ? x = y , 1 : 0;
}
point get_ins(line a, line b)
{
    double s1 = cross(b.b - a.a, a.b - a.a), s2 = cross(b.a - a.a, a.b - a.a);
    return {(s1 * b.a.x - s2 * b.b.x) / (s1 - s2),
            (s1 * b.a.y - s2 * b.b.y) / (s1 - s2)};
}
bool cmp(point a, point b) {
    if(sign(cross(a - low, b - low)) > 0)
        return true;
    if(sign(cross(a - low, b - low)) == 0 && sign(dis(low, a) - dis(low, b)) < 0)
        return true;
    return false;
}
bool check(point a, point b, point c) {
    return sign(cross(b - a, c - b)) <= 0;
}
void get_conv()
{
    sort(p + 1, p + n + 1, cmp);
    q[++ cnt] = low;
    for(int i = 1; i <= n; ++ i)
    {
        if(sign(p[i].x - low.x) == 0 && sign(p[i].y - low.y) == 0)
            continue;
        while(cnt > 1 && check(q[cnt - 1], q[cnt], p[i]))
            -- cnt;
        q[++ cnt] = p[i];
    }
    q[cnt + 1] = q[1];
    return ;
}
void get_ans(int i, int t, int l, int r)
{
    ans[1] = get_ins(line(q[l], q[l] + (q[i + 1] - q[i]).rotate()),
    line(q[i], q[i + 1]));
    ans[2] = get_ins(line(q[r], q[r] + (q[i + 1] - q[i]).rotate()),
    line(q[i], q[i + 1]));
    ans[3] = get_ins(line(q[r], q[r] + (q[i + 1] - q[i]).rotate()),
    line(q[t], q[t] + q[i + 1] - q[i]));
    ans[4] = get_ins(line(q[l], q[l] + (q[i + 1] - q[i]).rotate()),
    line(q[t], q[t] + q[i + 1] - q[i]));
    return ;
}

signed main()
{
   // freopen(".in", "r", stdin);
   // freopen(".out", "w", stdout);
    read(n), low.y = 1e6;
    for(int i = 1; i <= n; ++ i)
        scanf("%lf%lf", &p[i].x, &p[i].y), low = (sign(p[i].y - low.y) < 0 ||
        (sign(p[i].y - low.y) == 0 && sign(p[i].x - low.x) < 0)) ? p[i] : low;
    get_conv();
    for(int i = 1, t = 2, l = 2, r = 2; i <= cnt; ++ i)
    {
        double d = dis(q[i], q[i + 1]);
        while(sign(cross(q[t] - q[i], q[t] - q[i + 1]) -
        cross(q[t + 1] - q[i], q[t + 1] - q[i + 1])) < 0)
            t = t % cnt + 1;
        l = t;
        while(sign(dot(q[r + 1] - q[r], q[i + 1] - q[i])) > 0)
            r = r % cnt + 1;
        while(sign(dot(q[l + 1] - q[l], q[i + 1] - q[i])) < 0)
            l = l % cnt + 1;
        double res = cross(q[i + 1] - q[i], q[t] - q[i]) *
        (d + fabs(dot(q[i + 1] - q[i], q[r] - q[i + 1]) / d) +
        fabs(dot(q[l] - q[i], q[i + 1] - q[i]) / d)) / d;
        if(sign(res - S) < 0)
            S = res, get_ans(i, t, l, r);
    }
    printf("%lf\n", S);
    for(int i = 1; i <= 4; ++ i)
    {
        double x = ans[i].x, y = ans[i].y;
        if(sign(x) == 0)
            x = 0.0;
        if(sign(y) == 0)
            y = 0.0;
        printf("%lf %lf\n", x, y);
    }
    return 0;
} 

尾声

笔者也只凑的出来这一点了…