凸包是一个平面中给定一组点的最小凸多边形。简单来说，凸包可以看作是一个“围住”所有点的橡皮带的形状。当你把一根橡皮带围住这些点时，它的形状即为这些点的凸包。
最小性: 凸包是包围给定点集的最小凸多边形。这意味着它的边界点是点集中边界的点。
凸性: 凸包内部的任意两点之间的连线都完全位于凸包内。
边界点: 凸包的边界由输入点集中的一部分点构成，且这些边界点都是形成凸包的最外层点。
唯一性: 对于任意一组点，其凸包是唯一的，但在某些情况下（如有多个点重合），凸包的形式可能会有多个相同的边界。
拓扑性质: 凸包在拓扑学中是一个重要的概念，许多关于点集的性质（如连通性和紧致性）在研究凸包时得以应用。
可分解性: 一个多边形的凸包可以被进一步分解为多个简单的几何形状（如三角形），这在计算几何中很有用。
算法思想
Andrew 算法（也称为单调链算法）是一种求解二维平面上点集凸包的高效算法。它的核心思想是先将所有点按照 x 坐标（如果 x 坐标相同，则按照 y 坐标）进行排序，然后通过构建上凸壳和下凸壳，最后将两者合并来形成整个凸包。
算法流程
- 点排序：
- 首先按照 x 坐标对所有点进行排序，如果 x 坐标相同，则按照 y 坐标排序。
- 构建上凸壳：
- 初始化一个空的栈（或数组）用于存储上凸壳的顶点。
- 依次遍历排序后的点集：
- 每次加入一个新点时，检查当前栈顶的两个点与新点之间的关系。
- 如果新加入的点与前两个点构成的向量不满足逆时针方向（即叉积为负），则弹出栈顶点，直到形成一个逆时针方向的折线段。
- 将新点加入栈中。
- 最终栈中的点即为上凸壳的顶点。
- 构建下凸壳：
- 与上凸壳类似，只不过遍历方向从右到左。
- 初始化一个空的栈（或数组）用于存储下凸壳的顶点。
- 依次遍历排序后的点集（从右到左）：
- 每次加入一个新点时，检查当前栈顶的两个点与新点之间的关系。
- 如果新加入的点与前两个点构成的向量不满足逆时针方向（即叉积为负），则弹出栈顶点，直到形成一个逆时针方向的折线段。
- 将新点加入栈中。
- 最终栈中的点即为下凸壳的顶点。
- 合并上凸壳和下凸壳：
- 上凸壳的最后一个点和下凸壳的第一个点是相同的（最左端点），需要去重。
- 下凸壳的最后一个点和上凸壳的第一个点也是相同的（最右端点），需要去重。
- 合并上凸壳和下凸壳得到完整的凸包。
算法模板
using Point = std::pair<int, int>; // 使用 std::pair 来表示二维平面中的一个点
// 凸包算法（Andrew 算法实现）
std::vector<Point> convexHull(std::vector<Point> &points) {// 定义一个 lambda 函数，用于计算叉积auto cross = [](const Point &O, const Point &A, const Point &B) {// 将点的坐标进行解构绑定auto [Ox, Oy] = O; auto [Ax, Ay] = A; auto [Bx, By] = B;// 返回叉积的计算结果，判断点 O->A->B 的转向return (Ax - Ox) * (By - Oy) - (Ay - Oy) * (Bx - Ox);};// 按照 x 坐标（次要按 y 坐标）对点集进行排序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;
}
例题
P2742 圈奶牛Fencing the Cows /【模板】二维凸包
农夫约翰想要建造一个围栏用来围住他的奶牛，可是他资金匮乏。他建造的围栏必须包括他的奶牛喜欢吃草的所有地点。对于给出的这些地点的坐标，计算最短的能够围住这些点的围栏的长度。
#include<bits/stdc++.h>
using namespace std;using Point=pair<double,double>;vector<Point> convexHull(vector<Point> &points);double distance(const Point &A, const Point &B) { auto [Ax, Ay] = A; auto [Bx, By] = B;return hypot(Ax-Bx,Ay-By);
}int main() {int n;cin>>n;vector<Point> points(n);for(auto&[x,y]:points)cin>>x>>y;vector hull=convexHull(points);double ans=distance(hull.front(),hull.back());for(int i=1;i<hull.size();i++)ans+=distance(hull[i-1],hull[i]);cout<<fixed<<setprecision(2)<<ans<<endl;return 0;
}
