旋转卡壳算法是一种几何算法，主要用于在二维平面上求解与凸包相关的最优问题。该算法利用凸包顶点的顺序性和对称性，通过模拟两个卡壳（calipers）沿着凸包边界的旋转来寻找最优解。常见的应用包括计算凸包的直径（即最远点对之间的距离）、最小包围矩形（最小面积矩形），以及最小宽度（宽度最小的方向）。
算法思想
旋转卡壳算法的核心思想是通过模拟两个相互平行的“卡壳”在凸多边形的边缘上旋转，来找到特定的几何关系或最优解。该算法利用了凸多边形的凸性性质，使得在计算过程中可以高效地从一个顶点移动到下一个顶点，从而避免了暴力搜索中不必要的计算。
算法流程
以计算凸多边形的直径为例，下面是旋转卡壳算法的基本步骤：
- 构造凸包：
- 首先，给定一个点集，使用算法（如 Graham 扫描或 Andrew 算法）计算出该点集的凸包。凸包是最小的凸多边形，能够包含所有的点。
- 初始化卡壳：
- 选择凸包中的任意一个点作为起点，设定两个相互平行的卡壳（线段），其中一个卡壳与凸包的某一条边重合。通常选择一条凸包的边作为初始卡壳。
- 旋转卡壳：
- 开始模拟卡壳的旋转过程。具体来说，对于每个顶点，考虑卡壳与凸包边的夹角（即旋转的角度）。
- 将其中一个卡壳固定在当前边上，旋转另一个卡壳，使得它始终与凸包的一条边保持平行。旋转过程中，保持卡壳之间的距离最大化。
- 更新最优解：
- 在旋转过程中，每次更新卡壳时，计算卡壳之间的距离（即计算当前点对的距离）。记录并更新最大距离，直到卡壳旋转回到起始位置。
- 终止条件：
- 当卡壳旋转一周，回到初始位置时，算法终止。此时记录的最大距离即为凸多边形的直径。
算法模板
前置模板
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;
}
凸包直径
// 旋转卡壳算法求凸包的直径（即最远点对的距离）
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); // 返回凸包直径
}
例题
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;
}