拓冰网站定制 
文档教程知识库【免费下载链接】cp-algorithmsAlgorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)项目地址https://gitcode.com/GitHub_Trending/cp/cp-algorithms点击查看免费下载本文围绕 CP-Algorithms 仓库cp-algorithms中 凸包构建文章 的核心内容展开系统讲解从平面点集构造凸包的Graham 扫描Grahams scan与Monotone chainAndrew 算法两种经典算法覆盖算法原理、转向判定、共线点处理等关键细节并给出可直接复制运行的完整 C 实现。读完本文你将掌握两种 $\mathcal{O}(N\log N)$ 最优复杂度凸包算法的推导与实现并能借助仓库自带的测试用例test/test_convex_hull.cpp验证代码正确性。问题定义从点集到最小凸多边形给定平面上 $N$ 个点目标是构造这些点的凸包——即包含所有给定点的最小凸多边形。所谓“最小”是指不存在更小的凸多边形能包住这组点凸包的顶点全部来自输入点集且每个顶点都无法被其余顶点围成的任意直线“包住”。本文介绍的两种算法均于上世纪末提出Graham 扫描由 Graham 于 1972 年发表Monotone chain由 Andrew 于 1979 年发表。两者复杂度均为 $\mathcal{O}(N\log N)$且从渐近意义上是最优的——已经证明不存在渐近更优的通用算法少数需要并行或在线处理的特殊问题除外。该结论意味着任何仅基于比较的凸包算法排序阶段 $\Omega(N\log N)$ 的下界无法突破。前置基础用叉积判定转向两种算法都依赖一个核心几何操作判断三个点的转向方向顺时针 / 逆时针 / 共线。这是通过二维叉积伪标量积实现的具体原理可参考仓库中 有向三角形面积 与 基础几何 两篇文章。对于三个点 $a, b, c$叉积值 $v a.x\times(b.y-c.y)b.x\times(c.y-a.y)c.x\times(a.y-b.y)$ 的符号含义为叉积值转向$v 0$顺时针clockwise$v 0$逆时针counter-clockwise$v 0$共线collinear这个值本质上就是三角形有向面积的 $2$ 倍参见 有向三角形面积 中的行列式推导。两种凸包算法围绕它分别封装了cw顺时针与ccw逆时针判定函数并支持通过include_collinear参数决定是否把共线点纳入结果。算法一Graham 扫描算法流程寻找基准点 $P_0$找出最底部的点。若存在多个相同 $Y$ 坐标的点取 $X$ 坐标更小的那个。此步骤耗时 $\mathcal{O}(N)$。极角排序将其余所有点按相对 $P_0$ 的极角顺时针排序。若两个或多个点极角相同按它们到 $P_0$ 的距离升序打破平局。线性扫描构造逐个遍历排序后的点维护一个栈。每加入一个新点检查“当前点 栈顶前两个点”是否构成顺时针转向若不是即构成逆时针或共线且不允许共线时则弹出栈顶的前一个点因为它会导致非凸形状。收尾当遍历回到起点 $P_0$ 时算法结束栈中保存的即凸包全部顶点按顺时针顺序排列。转向判断的几何直觉是在逆时针扫描过程中凸包边界上的连续三条边必须保持同一转向方向一旦出现反向转折说明中间那个点可以被新点“包住”理应被丢弃。共线点的处理若需要把共线点也纳入凸包例如题目要求输出边上所有点排序之后还需额外一步找出与 $P_0$共线且极角距离最大的点这些点应位于排序后向量末尾将这条共线线段上的点顺序反转使得算法能依次输出全部共线点否则算法只取到该直线上最近的点就停止了。需要特别注意这一步绝不能用于不包含共线点的版本否则得到的将不是最小凸包。完整实现以下是仓库 凸包构建文章 中的 Graham 扫描实现graham_scan代码块含逐行说明struct pt { double x, y; bool operator (pt const t) const { return x t.x y t.y; } }; // 叉积判定0 顺时针0 逆时针0 共线 int orientation(pt a, pt b, pt c) { double v a.x*(b.y-c.y)b.x*(c.y-a.y)c.x*(a.y-b.y); if (v 0) return -1; // clockwise if (v 0) return 1; // counter-clockwise return 0; } // include_collineartrue 时共线也算“合格”的顺时针 bool cw(pt a, pt b, pt c, bool include_collinear) { int o orientation(a, b, c); return o 0 || (include_collinear o 0); } bool collinear(pt a, pt b, pt c) { return orientation(a, b, c) 0; } void convex_hull(vectorpt a, bool include_collinear false) { // 1) 找最底部、同 Y 时取最左的点作为 P0 pt p0 *min_element(a.begin(), a.end(), [](pt a, pt b) { return make_pair(a.y, a.x) make_pair(b.y, b.x); }); // 2) 按相对 P0 的极角顺时针排序极角相同时按距离升序 sort(a.begin(), a.end(), p0 { int o orientation(p0, a, b); if (o 0) return (p0.x-a.x)*(p0.x-a.x) (p0.y-a.y)*(p0.y-a.y) (p0.x-b.x)*(p0.x-b.x) (p0.y-b.y)*(p0.y-b.y); return o 0; }); // 3) 若需要共线点反转与 P0 共线且距离最远的那段保证输出全部边上的点 if (include_collinear) { int i (int)a.size()-1; while (i 0 collinear(p0, a[i], a.back())) i--; reverse(a.begin()i1, a.end()); } // 4) 线性扫描 栈维护 vectorpt st; for (int i 0; i (int)a.size(); i) { while (st.size() 1 !cw(st[st.size()-2], st.back(), a[i], include_collinear)) st.pop_back(); st.push_back(a[i]); } // 5) 处理退化情形不允许共线且最终只剩两个重合点时去重 if (include_collinear false st.size() 2 st[0] st[1]) st.pop_back(); a st; }代码要点解读排序比较器中当orientation(p0, a, b) 0时按到 $P_0$ 距离的平方升序比较从而避开浮点开方同时实现文档所述的“同极角按距离升序”的平局规则第 3 步的reverse只作用于“与 $P_0$ 共线且极角最远”的后缀段正是文档强调的共线点输出关键函数原地修改传入的vectorpt a最终a即顺时针排列的凸包顶点。算法二Monotone chainAndrew 算法算法流程寻找左右端点 A 与 B先找最左与最右的点。若最左侧存在多个点取其中 $Y$ 坐标最低的作为 A若最右侧存在多个点取其中 $Y$ 坐标最高的作为 B。A、B 必然属于凸包——它们相距最远不可能被任意两点连成的直线“包住”。按直线 AB 划分点集连接 A、B 画一条线将所有点分成两个集合——直线上方的 $S_1$ 和下方的 $S_2$落在直线 AB 上的点可归入任意一侧A、B 同时属于两个集合。算法分别构造上链 $S_1$与下链 $S_2$最后合并得到答案。上链构造将所有点按 $X$ 坐标排序。当前点属于上链的条件是它是最后一个点即 B或者“A 到当前点”与“当前点到 B”两条连线的转向是顺时针。判定可复用文档中的 orientation。点加入上链时检查上链倒数第二点与最后一点的连线、最后一点与当前点的连线所成角度若该角度不是顺时针则移除最近加入上链的点——因为一旦当前点入链它将包含包住之前的那个点。下链构造逻辑与上链对称当前点属于下链的条件是它是 B或者“A 到当前点”与“当前点到 B”两条连线的转向是逆时针。加入下链时检查的角度若不是逆时针同样弹出最近加入下链的点。合并最终凸包由上链与下链合并而成整体呈顺时针顺序实现如下。共线与退化情形若需要共线点只需在顺时针/逆时针判定例程中把共线情况视为“合格”即可见下方cw/ccw的include_collinear分支。但这会引入一个退化情形当所有输入点共线于同一条直线时算法会输出重复点。解决办法是检查上链是否包含全部点——若是直接反转返回这些点这恰好与 Graham 实现在该场景下的输出一致。完整实现以下是仓库文章中的 Monotone chain 实现monotone_chain代码块struct pt { double x, y; }; int orientation(pt a, pt b, pt c) { double v a.x*(b.y-c.y)b.x*(c.y-a.y)c.x*(a.y-b.y); if (v 0) return -1; // clockwise if (v 0) return 1; // counter-clockwise return 0; } bool cw(pt a, pt b, pt c, bool include_collinear) { int o orientation(a, b, c); return o 0 || (include_collinear o 0); } bool ccw(pt a, pt b, pt c, bool include_collinear) { int o orientation(a, b, c); return o 0 || (include_collinear o 0); } void convex_hull(vectorpt a, bool include_collinear false) { if (a.size() 1) return; // 按 (x, y) 字典序排序两端即最左/最右点 sort(a.begin(), a.end(), [](pt a, pt b) { return make_pair(a.x, a.y) make_pair(b.x, b.y); }); pt p1 a[0], p2 a.back(); vectorpt up, down; up.push_back(p1); down.push_back(p1); // 一次遍历同时构造上链与下链 for (int i 1; i (int)a.size(); i) { if (i a.size() - 1 || cw(p1, a[i], p2, include_collinear)) { while (up.size() 2 !cw(up[up.size()-2], up[up.size()-1], a[i], include_collinear)) up.pop_back(); up.push_back(a[i]); } if (i a.size() - 1 || ccw(p1, a[i], p2, include_collinear)) { while (down.size() 2 !ccw(down[down.size()-2], down[down.size()-1], a[i], include_collinear)) down.pop_back(); down.push_back(a[i]); } } // 退化情形所有点共线且需要共线点时直接反转输出 if (include_collinear up.size() a.size()) { reverse(a.begin(), a.end()); return; } // 合并上链 下链去掉首尾重复点 a.clear(); for (int i 0; i (int)up.size(); i) a.push_back(up[i]); for (int i down.size() - 2; i 0; i--) a.push_back(down[i]); }实现细节说明通过(x, y)字典序排序一次完成“按 $X$ 排序 确定 A、B”两个目标因此 Monotone chain 无需显式计算极角避免了浮点三角运算第 2 步中的“属于上链”判定i a.size() - 1 || cw(p1, a[i], p2, ...)与“属于下链”判定i a.size() - 1 || ccw(p1, a[i], p2, ...)在同一循环内对每个点各执行一次利用||短路使得端点 B 同时进入两条链合并时下链从down.size() - 2到1逆序拼接跳过 A 与 B 的重复出现最终得到顺时针的完整凸包当输入只有一个点时直接返回无需任何处理。两种算法的对比与选型维度Graham 扫描Monotone chain发布时间1972Graham1979Andrew排序依据相对基准点的极角需比较角度$(x, y)$ 字典序纯坐标比较几何运算只需叉积判转向但排序时按极角比较全程只需叉积判转向共线点支持需额外反转共线后缀段通过cw/ccw的include_collinear开关即可退化处理需去除重合点需检测“全部点共线”情形两者都是 $\mathcal{O}(N\log N)$ 最优算法。Monotone chain 因为排序基于纯坐标字典序、不依赖角度比较通常实现更简洁、浮点误差暴露面更小是竞赛实践中更常用的版本而 Graham 扫描概念上更直观适合教学与理解“极角排序 单调栈”的核心思想。仓库文章在 导航结构 中将本文归类于 Geometry 下的 Convex hull 分类与 凸包 Trick / Li Chao 树 相邻后者处理的是另一类“凸包优化”问题与本文的点集凸包构建是互补关系。仓库源码级验证测试用例与运行方式为确保两段实现正确仓库提供了一套完整的测试基础设施可作为读者验证与学习的范本。测试用例结构测试驱动文件test/test_convex_hull.cpp测试数据test/data/convex_hull.h代码片段提取工具test/extract_snippets.py批量编译运行脚本test/test.sh。片段提取机制test/extract_snippets.py 用正则表达式^\s*\{.cpp\sfile(\S)\}$扫描src/目录下所有 Markdown 文档把标注了file名字的代码块抽取为对应的*.h头文件。也就是说convex-hull.md中的graham_scan与monotone_chain两个代码块会被自动生成为graham_scan.h与monotone_chain.h保证文档中的代码与测试编译的是同一份源码避免文档与实现脱节。测试策略test/test_convex_hull.cpp 通过命名空间隔离同时包含两套实现namespace GrahamScan { #include graham_scan.h } namespace MonotoneChain { #include monotone_chain.h } #include data/convex_hull.h对每组测试数据(points, ans, ans_col)分别用include_collinear false与true运行两种算法断言结果点数与期望答案一致assert(hull.size() ans.size()/2)由于凸包允许从任意顶点开始测试先把期望答案复制拼接ans.insert(ans.end(), ans.begin(), ans.end())再用search在拼接序列中匹配旋转后的实际输出从而兼容任意起始顶点。测试数据的边界覆盖test/data/convex_hull.h 中的ConvexHull结构体同时保存普通凸包convex_hull与含共线点的凸包convex_hull_collinear覆盖了一般随机点集如 8~100 个点与对应的期望凸包共线边界点如{{0,0},{1,0},{2,0},{0,1},{2,1}}这类边上含中间点的输入验证共线点输出正确退化单线情形文档明确讨论的场景如{{0,0},{1,1},{2,2}}、{{0,0},{0,1},{0,2},{0,3}}、{{0,0},{1,0},{2,0},{3,0}}对应 Graham 与 Monotone chain 各自的退化处理分支去重合点 / 检测上链含全部点后反转。运行方式在仓库根目录执行脚本运行于test/目录cd test ./test.shtest/test.sh 首先调用python extract_snippets.py生成头文件随后用g -stdc17 -fsanitizeundefined -fno-sanitize-recover可通过环境变量CXX指定编译器逐个编译test/*.cpp并运行全程开启 UndefinedBehaviorSanitizer 以捕获未定义行为。若需清理生成的头文件执行 test/clean.sh。复杂度分析与适用场景两个算法的复杂度完全一致阶段复杂度排序$\mathcal{O}(N\log N)$线性扫描栈维护$\mathcal{O}(N)$每个点至多入栈/出栈一次总计$\mathcal{O}(N\log N)$空间$\mathcal{O}(N)$存储排序结果与栈由于排序阶段已触及基于比较算法的理论下界两者均为渐近最优。适用场景包括几何基础构件凸包是碰撞检测、图像轮廓提取、最小外接矩形等问题的前置步骤与仓库其他文章配合构造出凸包后可进一步用于 判断点在凸多边形内$\mathcal{O}(\log N)$、凸包 Trick / Li Chao 树 等后续算法竞赛实战适合坐标规模较大$N$ 达 $10^5$ 级的凸包题此时 $\mathcal{O}(N\log N)$ 是标准最优解。练习题目原文档提供了以下可用于巩固算法理解的练习题目按平台与题号列出可在对应 OJ 平台检索Kattis - Convex HullconvexhullKattis - Keep the Parade SafeparadeCodeforces - I. Birthday2172/ILatin American Regionals 2006 - Onion Layers9413Timus 1185: Wall1185USACO 2014 January Contest, Gold - Cow Curlingcpid382建议按“一般点集 → 含共线点 → 全部点共线”的顺序刷题重点体会两种实现中退化分支被触发时的行为差异。赞分享文档教程知识库【免费下载链接】cp-algorithmsAlgorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)项目地址https://gitcode.com/GitHub_Trending/cp/cp-algorithms点击查看免费下载相关推荐凸包算法终极指南Graham扫描与Jarvis步进完全解析凸包算法终极指南Graham扫描与Jarvis步进完全解析 在计算几何领域凸包算法是解决点集边界问题的核心技术广泛应用于计算机图形学、地理信息系统和模式识文档教程知识库GitHub_Trending/cp/cp-algorithms实操测评算法实现效率与正确性验证GitHub_Trending/cp/cp algorithms实操测评算法实现效率与正确性验证 你是否还在为算法学习中看懂原理却写不对代码而困扰是否遇文档教程知识库Mac Mouse Fix 完整指南把普通鼠标调出 Mac 触控板级的体验Mac Mouse Fix 完整指南把普通鼠标调出 Mac 触控板级的体验 第一次把第三方鼠标插到 Mac 上最常见的两个挫败侧键点了没反应滚轮一格一格桌面应用系统编程上一篇res-downloader 完整上手指南跨平台资源嗅探5 分钟下载视频号、抖音、m3u8下一篇Tinke高效实用的NDS游戏文件编辑与汉化工具创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 CP-Algorithms 凸包构建指南：Graham 扫描与 Monotone Chain 算法实现与验证
文档教程知识库【免费下载链接】cp-algorithmsAlgorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)项目地址https://gitcode.com/GitHub_Trending/cp/cp-algorithms点击查看免费下载本文围绕 CP-Algorithms 仓库cp-algorithms中 凸包构建文章 的核心内容展开系统讲解从平面点集构造凸包的Graham 扫描Grahams scan与Monotone chainAndrew 算法两种经典算法覆盖算法原理、转向判定、共线点处理等关键细节并给出可直接复制运行的完整 C 实现。读完本文你将掌握两种 $\mathcal{O}(N\log N)$ 最优复杂度凸包算法的推导与实现并能借助仓库自带的测试用例test/test_convex_hull.cpp验证代码正确性。问题定义从点集到最小凸多边形给定平面上 $N$ 个点目标是构造这些点的凸包——即包含所有给定点的最小凸多边形。所谓“最小”是指不存在更小的凸多边形能包住这组点凸包的顶点全部来自输入点集且每个顶点都无法被其余顶点围成的任意直线“包住”。本文介绍的两种算法均于上世纪末提出Graham 扫描由 Graham 于 1972 年发表Monotone chain由 Andrew 于 1979 年发表。两者复杂度均为 $\mathcal{O}(N\log N)$且从渐近意义上是最优的——已经证明不存在渐近更优的通用算法少数需要并行或在线处理的特殊问题除外。该结论意味着任何仅基于比较的凸包算法排序阶段 $\Omega(N\log N)$ 的下界无法突破。前置基础用叉积判定转向两种算法都依赖一个核心几何操作判断三个点的转向方向顺时针 / 逆时针 / 共线。这是通过二维叉积伪标量积实现的具体原理可参考仓库中 有向三角形面积 与 基础几何 两篇文章。对于三个点 $a, b, c$叉积值 $v a.x\times(b.y-c.y)b.x\times(c.y-a.y)c.x\times(a.y-b.y)$ 的符号含义为叉积值转向$v 0$顺时针clockwise$v 0$逆时针counter-clockwise$v 0$共线collinear这个值本质上就是三角形有向面积的 $2$ 倍参见 有向三角形面积 中的行列式推导。两种凸包算法围绕它分别封装了cw顺时针与ccw逆时针判定函数并支持通过include_collinear参数决定是否把共线点纳入结果。算法一Graham 扫描算法流程寻找基准点 $P_0$找出最底部的点。若存在多个相同 $Y$ 坐标的点取 $X$ 坐标更小的那个。此步骤耗时 $\mathcal{O}(N)$。极角排序将其余所有点按相对 $P_0$ 的极角顺时针排序。若两个或多个点极角相同按它们到 $P_0$ 的距离升序打破平局。线性扫描构造逐个遍历排序后的点维护一个栈。每加入一个新点检查“当前点 栈顶前两个点”是否构成顺时针转向若不是即构成逆时针或共线且不允许共线时则弹出栈顶的前一个点因为它会导致非凸形状。收尾当遍历回到起点 $P_0$ 时算法结束栈中保存的即凸包全部顶点按顺时针顺序排列。转向判断的几何直觉是在逆时针扫描过程中凸包边界上的连续三条边必须保持同一转向方向一旦出现反向转折说明中间那个点可以被新点“包住”理应被丢弃。共线点的处理若需要把共线点也纳入凸包例如题目要求输出边上所有点排序之后还需额外一步找出与 $P_0$共线且极角距离最大的点这些点应位于排序后向量末尾将这条共线线段上的点顺序反转使得算法能依次输出全部共线点否则算法只取到该直线上最近的点就停止了。需要特别注意这一步绝不能用于不包含共线点的版本否则得到的将不是最小凸包。完整实现以下是仓库 凸包构建文章 中的 Graham 扫描实现graham_scan代码块含逐行说明struct pt { double x, y; bool operator (pt const t) const { return x t.x y t.y; } }; // 叉积判定0 顺时针0 逆时针0 共线 int orientation(pt a, pt b, pt c) { double v a.x*(b.y-c.y)b.x*(c.y-a.y)c.x*(a.y-b.y); if (v 0) return -1; // clockwise if (v 0) return 1; // counter-clockwise return 0; } // include_collineartrue 时共线也算“合格”的顺时针 bool cw(pt a, pt b, pt c, bool include_collinear) { int o orientation(a, b, c); return o 0 || (include_collinear o 0); } bool collinear(pt a, pt b, pt c) { return orientation(a, b, c) 0; } void convex_hull(vectorpt a, bool include_collinear false) { // 1) 找最底部、同 Y 时取最左的点作为 P0 pt p0 *min_element(a.begin(), a.end(), [](pt a, pt b) { return make_pair(a.y, a.x) make_pair(b.y, b.x); }); // 2) 按相对 P0 的极角顺时针排序极角相同时按距离升序 sort(a.begin(), a.end(), p0 { int o orientation(p0, a, b); if (o 0) return (p0.x-a.x)*(p0.x-a.x) (p0.y-a.y)*(p0.y-a.y) (p0.x-b.x)*(p0.x-b.x) (p0.y-b.y)*(p0.y-b.y); return o 0; }); // 3) 若需要共线点反转与 P0 共线且距离最远的那段保证输出全部边上的点 if (include_collinear) { int i (int)a.size()-1; while (i 0 collinear(p0, a[i], a.back())) i--; reverse(a.begin()i1, a.end()); } // 4) 线性扫描 栈维护 vectorpt st; for (int i 0; i (int)a.size(); i) { while (st.size() 1 !cw(st[st.size()-2], st.back(), a[i], include_collinear)) st.pop_back(); st.push_back(a[i]); } // 5) 处理退化情形不允许共线且最终只剩两个重合点时去重 if (include_collinear false st.size() 2 st[0] st[1]) st.pop_back(); a st; }代码要点解读排序比较器中当orientation(p0, a, b) 0时按到 $P_0$ 距离的平方升序比较从而避开浮点开方同时实现文档所述的“同极角按距离升序”的平局规则第 3 步的reverse只作用于“与 $P_0$ 共线且极角最远”的后缀段正是文档强调的共线点输出关键函数原地修改传入的vectorpt a最终a即顺时针排列的凸包顶点。算法二Monotone chainAndrew 算法算法流程寻找左右端点 A 与 B先找最左与最右的点。若最左侧存在多个点取其中 $Y$ 坐标最低的作为 A若最右侧存在多个点取其中 $Y$ 坐标最高的作为 B。A、B 必然属于凸包——它们相距最远不可能被任意两点连成的直线“包住”。按直线 AB 划分点集连接 A、B 画一条线将所有点分成两个集合——直线上方的 $S_1$ 和下方的 $S_2$落在直线 AB 上的点可归入任意一侧A、B 同时属于两个集合。算法分别构造上链 $S_1$与下链 $S_2$最后合并得到答案。上链构造将所有点按 $X$ 坐标排序。当前点属于上链的条件是它是最后一个点即 B或者“A 到当前点”与“当前点到 B”两条连线的转向是顺时针。判定可复用文档中的 orientation。点加入上链时检查上链倒数第二点与最后一点的连线、最后一点与当前点的连线所成角度若该角度不是顺时针则移除最近加入上链的点——因为一旦当前点入链它将包含包住之前的那个点。下链构造逻辑与上链对称当前点属于下链的条件是它是 B或者“A 到当前点”与“当前点到 B”两条连线的转向是逆时针。加入下链时检查的角度若不是逆时针同样弹出最近加入下链的点。合并最终凸包由上链与下链合并而成整体呈顺时针顺序实现如下。共线与退化情形若需要共线点只需在顺时针/逆时针判定例程中把共线情况视为“合格”即可见下方cw/ccw的include_collinear分支。但这会引入一个退化情形当所有输入点共线于同一条直线时算法会输出重复点。解决办法是检查上链是否包含全部点——若是直接反转返回这些点这恰好与 Graham 实现在该场景下的输出一致。完整实现以下是仓库文章中的 Monotone chain 实现monotone_chain代码块struct pt { double x, y; }; int orientation(pt a, pt b, pt c) { double v a.x*(b.y-c.y)b.x*(c.y-a.y)c.x*(a.y-b.y); if (v 0) return -1; // clockwise if (v 0) return 1; // counter-clockwise return 0; } bool cw(pt a, pt b, pt c, bool include_collinear) { int o orientation(a, b, c); return o 0 || (include_collinear o 0); } bool ccw(pt a, pt b, pt c, bool include_collinear) { int o orientation(a, b, c); return o 0 || (include_collinear o 0); } void convex_hull(vectorpt a, bool include_collinear false) { if (a.size() 1) return; // 按 (x, y) 字典序排序两端即最左/最右点 sort(a.begin(), a.end(), [](pt a, pt b) { return make_pair(a.x, a.y) make_pair(b.x, b.y); }); pt p1 a[0], p2 a.back(); vectorpt up, down; up.push_back(p1); down.push_back(p1); // 一次遍历同时构造上链与下链 for (int i 1; i (int)a.size(); i) { if (i a.size() - 1 || cw(p1, a[i], p2, include_collinear)) { while (up.size() 2 !cw(up[up.size()-2], up[up.size()-1], a[i], include_collinear)) up.pop_back(); up.push_back(a[i]); } if (i a.size() - 1 || ccw(p1, a[i], p2, include_collinear)) { while (down.size() 2 !ccw(down[down.size()-2], down[down.size()-1], a[i], include_collinear)) down.pop_back(); down.push_back(a[i]); } } // 退化情形所有点共线且需要共线点时直接反转输出 if (include_collinear up.size() a.size()) { reverse(a.begin(), a.end()); return; } // 合并上链 下链去掉首尾重复点 a.clear(); for (int i 0; i (int)up.size(); i) a.push_back(up[i]); for (int i down.size() - 2; i 0; i--) a.push_back(down[i]); }实现细节说明通过(x, y)字典序排序一次完成“按 $X$ 排序 确定 A、B”两个目标因此 Monotone chain 无需显式计算极角避免了浮点三角运算第 2 步中的“属于上链”判定i a.size() - 1 || cw(p1, a[i], p2, ...)与“属于下链”判定i a.size() - 1 || ccw(p1, a[i], p2, ...)在同一循环内对每个点各执行一次利用||短路使得端点 B 同时进入两条链合并时下链从down.size() - 2到1逆序拼接跳过 A 与 B 的重复出现最终得到顺时针的完整凸包当输入只有一个点时直接返回无需任何处理。两种算法的对比与选型维度Graham 扫描Monotone chain发布时间1972Graham1979Andrew排序依据相对基准点的极角需比较角度$(x, y)$ 字典序纯坐标比较几何运算只需叉积判转向但排序时按极角比较全程只需叉积判转向共线点支持需额外反转共线后缀段通过cw/ccw的include_collinear开关即可退化处理需去除重合点需检测“全部点共线”情形两者都是 $\mathcal{O}(N\log N)$ 最优算法。Monotone chain 因为排序基于纯坐标字典序、不依赖角度比较通常实现更简洁、浮点误差暴露面更小是竞赛实践中更常用的版本而 Graham 扫描概念上更直观适合教学与理解“极角排序 单调栈”的核心思想。仓库文章在 导航结构 中将本文归类于 Geometry 下的 Convex hull 分类与 凸包 Trick / Li Chao 树 相邻后者处理的是另一类“凸包优化”问题与本文的点集凸包构建是互补关系。仓库源码级验证测试用例与运行方式为确保两段实现正确仓库提供了一套完整的测试基础设施可作为读者验证与学习的范本。测试用例结构测试驱动文件test/test_convex_hull.cpp测试数据test/data/convex_hull.h代码片段提取工具test/extract_snippets.py批量编译运行脚本test/test.sh。片段提取机制test/extract_snippets.py 用正则表达式^\s*\{.cpp\sfile(\S)\}$扫描src/目录下所有 Markdown 文档把标注了file名字的代码块抽取为对应的*.h头文件。也就是说convex-hull.md中的graham_scan与monotone_chain两个代码块会被自动生成为graham_scan.h与monotone_chain.h保证文档中的代码与测试编译的是同一份源码避免文档与实现脱节。测试策略test/test_convex_hull.cpp 通过命名空间隔离同时包含两套实现namespace GrahamScan { #include graham_scan.h } namespace MonotoneChain { #include monotone_chain.h } #include data/convex_hull.h对每组测试数据(points, ans, ans_col)分别用include_collinear false与true运行两种算法断言结果点数与期望答案一致assert(hull.size() ans.size()/2)由于凸包允许从任意顶点开始测试先把期望答案复制拼接ans.insert(ans.end(), ans.begin(), ans.end())再用search在拼接序列中匹配旋转后的实际输出从而兼容任意起始顶点。测试数据的边界覆盖test/data/convex_hull.h 中的ConvexHull结构体同时保存普通凸包convex_hull与含共线点的凸包convex_hull_collinear覆盖了一般随机点集如 8~100 个点与对应的期望凸包共线边界点如{{0,0},{1,0},{2,0},{0,1},{2,1}}这类边上含中间点的输入验证共线点输出正确退化单线情形文档明确讨论的场景如{{0,0},{1,1},{2,2}}、{{0,0},{0,1},{0,2},{0,3}}、{{0,0},{1,0},{2,0},{3,0}}对应 Graham 与 Monotone chain 各自的退化处理分支去重合点 / 检测上链含全部点后反转。运行方式在仓库根目录执行脚本运行于test/目录cd test ./test.shtest/test.sh 首先调用python extract_snippets.py生成头文件随后用g -stdc17 -fsanitizeundefined -fno-sanitize-recover可通过环境变量CXX指定编译器逐个编译test/*.cpp并运行全程开启 UndefinedBehaviorSanitizer 以捕获未定义行为。若需清理生成的头文件执行 test/clean.sh。复杂度分析与适用场景两个算法的复杂度完全一致阶段复杂度排序$\mathcal{O}(N\log N)$线性扫描栈维护$\mathcal{O}(N)$每个点至多入栈/出栈一次总计$\mathcal{O}(N\log N)$空间$\mathcal{O}(N)$存储排序结果与栈由于排序阶段已触及基于比较算法的理论下界两者均为渐近最优。适用场景包括几何基础构件凸包是碰撞检测、图像轮廓提取、最小外接矩形等问题的前置步骤与仓库其他文章配合构造出凸包后可进一步用于 判断点在凸多边形内$\mathcal{O}(\log N)$、凸包 Trick / Li Chao 树 等后续算法竞赛实战适合坐标规模较大$N$ 达 $10^5$ 级的凸包题此时 $\mathcal{O}(N\log N)$ 是标准最优解。练习题目原文档提供了以下可用于巩固算法理解的练习题目按平台与题号列出可在对应 OJ 平台检索Kattis - Convex HullconvexhullKattis - Keep the Parade SafeparadeCodeforces - I. Birthday2172/ILatin American Regionals 2006 - Onion Layers9413Timus 1185: Wall1185USACO 2014 January Contest, Gold - Cow Curlingcpid382建议按“一般点集 → 含共线点 → 全部点共线”的顺序刷题重点体会两种实现中退化分支被触发时的行为差异。赞分享文档教程知识库【免费下载链接】cp-algorithmsAlgorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)项目地址https://gitcode.com/GitHub_Trending/cp/cp-algorithms点击查看免费下载相关推荐凸包算法终极指南Graham扫描与Jarvis步进完全解析凸包算法终极指南Graham扫描与Jarvis步进完全解析 在计算几何领域凸包算法是解决点集边界问题的核心技术广泛应用于计算机图形学、地理信息系统和模式识文档教程知识库GitHub_Trending/cp/cp-algorithms实操测评算法实现效率与正确性验证GitHub_Trending/cp/cp algorithms实操测评算法实现效率与正确性验证 你是否还在为算法学习中看懂原理却写不对代码而困扰是否遇文档教程知识库Mac Mouse Fix 完整指南把普通鼠标调出 Mac 触控板级的体验Mac Mouse Fix 完整指南把普通鼠标调出 Mac 触控板级的体验 第一次把第三方鼠标插到 Mac 上最常见的两个挫败侧键点了没反应滚轮一格一格桌面应用系统编程上一篇res-downloader 完整上手指南跨平台资源嗅探5 分钟下载视频号、抖音、m3u8下一篇Tinke高效实用的NDS游戏文件编辑与汉化工具创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考