【算法模板】计算几何：旋转卡壳求凸包直径

旋转卡壳算法是一种几何算法，主要用于在二维平面上求解与凸包相关的最优问题。该算法利用凸包顶点的顺序性和对称性，通过模拟两个卡壳（calipers）沿着凸包边界的旋转来寻找最优解。常见的应用包括计算凸包的直径（即最远点对之间的距离）、最小包围矩形（最小面积矩形），以及最小宽度（宽度最小的方向）。

算法思想

旋转卡壳算法的核心思想是通过模拟两个相互平行的“卡壳”在凸多边形的边缘上旋转，来找到特定的几何关系或最优解。该算法利用了凸多边形的凸性性质，使得在计算过程中可以高效地从一个顶点移动到下一个顶点，从而避免了暴力搜索中不必要的计算。

算法流程

以计算凸多边形的直径为例，下面是旋转卡壳算法的基本步骤：

1. 构造凸包：
   • 首先，给定一个点集，使用算法（如 Graham 扫描或 Andrew 算法）计算出该点集的凸包。凸包是最小的凸多边形，能够包含所有的点。
2. 初始化卡壳：
   • 选择凸包中的任意一个点作为起点，设定两个相互平行的卡壳（线段），其中一个卡壳与凸包的某一条边重合。通常选择一条凸包的边作为初始卡壳。
3. 旋转卡壳：
   • 开始模拟卡壳的旋转过程。具体来说，对于每个顶点，考虑卡壳与凸包边的夹角（即旋转的角度）。
   • 将其中一个卡壳固定在当前边上，旋转另一个卡壳，使得它始终与凸包的一条边保持平行。旋转过程中，保持卡壳之间的距离最大化。
4. 更新最优解：
   • 在旋转过程中，每次更新卡壳时，计算卡壳之间的距离（即计算当前点对的距离）。记录并更新最大距离，直到卡壳旋转回到起始位置。
5. 终止条件：
   • 当卡壳旋转一周，回到初始位置时，算法终止。此时记录的最大距离即为凸多边形的直径。

算法模板

前置模板

using Real = double;  // 定义浮点数类型为 Real
using Point = std::pair<Real, Real>; // 使用 std::pair 来表示二维平面中的一个点

// 计算向量 AB 和向量 AC 的叉积
Real cross(const Point& A, const Point& B, const Point& C) {
    auto [Ax, Ay] = A; auto [Bx, By] = B; auto [Cx, Cy] = C;
    return (Bx - Ax) * (Cy - Ay) - (By - Ay) * (Cx - Ax);
}

// 计算向量 AB 和向量 AC 的点积
Real dot(const Point& A, const Point& B, const Point& C) {
    auto [Ax, Ay] = A; auto [Bx, By] = B; auto [Cx, Cy] = C;
    return (Bx - Ax) * (Cx - Ax) + (By - Ay) * (Cy - Ay);
}

// 计算两点之间的距离平方
Real distanceSquared(const Point& A, const Point& B) {
    return dot(A,B,B);
}

// 计算两点之间的欧几里得距离
Real distance(const Point& A, const Point& B) {
    return std::sqrt(distanceSquared(A, B));
}

// 凸包算法（Andrew 算法实现）
std::vector<Point> convexHull(std::vector<Point>& points) {
    std::sort(points.begin(), points.end());
    std::vector<Point> hull;
    for (const Point& p : points) {
        while (hull.size() >= 2 && cross(hull[hull.size() - 2], hull.back(), p) <= 0)
            hull.pop_back();
        hull.push_back(p);
    }
    size_t t = hull.size() + 1;
    for (int i = points.size() - 1; i >= 0; --i) {
        while (hull.size() >= t && cross(hull[hull.size() - 2], hull.back(), points[i]) <= 0)
            hull.pop_back();
        hull.push_back(points[i]);
    }
    hull.pop_back();
    return hull;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

凸包直径

// 旋转卡壳算法求凸包的直径（即最远点对的距离）
Real rotatingCalipers(const std::vector<Point>& hull) {
    int n = hull.size(); // 获取凸包点的数量

    // 如果凸包只有一个点，直径为0
    if (n == 1) return 0;

    Real maxDist = 0; // 初始化最大距离的平方为0
    int j = 1; // j 是与 i 相对的点的索引

    // 遍历凸包上的每个点 i
    for (int i = 0; i < n; ++i) {
        // 通过旋转卡壳，找到使距离最大化的点 j
        while (cross(hull[i], hull[(i + 1) % n], hull[(j + 1) % n]) >= 
               cross(hull[i], hull[(i + 1) % n], hull[j])) {
            // 如果 j 的下一个点与 i 的距离更大，则更新 j
            j = (j + 1) % n;
        }
        // 更新最大距离的平方
        maxDist = std::max(maxDist, distanceSquared(hull[i], hull[j]));
        maxDist = std::max(maxDist, distanceSquared(hull[(i + 1) % n], hull[j]));
    }

    return sqrtl(maxDist); // 返回凸包直径
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

例题

H-Two Convex Polygons_2024牛客暑期多校训练营9 (nowcoder.com)

在二维平面上，给定两个凸多边形 A 和 B（可能有三个共线点）。其中，A 是固定的。你可以在平面上平移、旋转或翻转 B，但要确保 A 和 B 至少有一个点重合。求 B 可能覆盖的图形的周长。

#include <bits/stdc++.h>
using namespace std;

using Real = long double;
using Point = std::pair<Real, Real>; 
Real cross(const Point &A, const Point &B, const Point &C);
Real distanceSquared(const Point &A, const Point &B);
Real rotatingCalipers(const std::vector<Point> &hull);

signed main(){
    int task;
    cin >> task;
    while (task--){
        int n;
        cin >> n;
        vector<Point> vpa(n);
        for (auto &[x, y] : vpa){
            int _x,_y;
            cin>>_x>>_y;
            x=_x,y=_y;
        }
        int m;
        cin >> m;
        vector<Point> vpb(m);
        for (auto &[x, y] : vpb){
            int _x,_y;
            cin>>_x>>_y;
            x=_x,y=_y;
        }

        long double ans = 0;
        for (int i = 1; i <= n; i++)
            ans += sqrtl(distanceSquared(vpa[i - 1], vpa[(i) % n]));
        long double R = rotatingCalipers(vpb);
        ans += R * M_PI * 2;
        cout << ans << endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39