凸包基础 - ”将进酒,杯莫停“
2026-07-14 17:30:04
发布于:浙江
自主学习笔记类产物
——————————————————————————————————————————
前置
一.Graham扫描法

比较重要的是第四步。
三点构成两条线。



在后面的计算,我们把三个点变成两个向量。



逆时针作为正方向。
判断是否为逆时针:叉积。
为什么不用点积?点击:
sin:一二象限为正,三四象限为负。
就【判断是否向正方向移动。
好的,来看看苹果:
1.从点集中选出一个最靠近左下方的点
2.以选定的基准点为极点,对其他点按照极角进行逆时针排序。如果极角相同,则根据与基准点的距离排序,距离近的点优先。
3.使用一个栈来维护当前的凸包顶点。首先将基准点和排序后的第一个点压入栈中。
4.遍历排序后的点:从第三个点开始,对于每个点,检查它与栈顶的两个点形成的角度(使用叉积),如果符合要求则将点压入栈中,不符合则弹出栈顶的点,重复检查直到符合要求。


这是我从洛谷第一个题解截的图:它是如何根据极差将点排序的。





放置一道变式题目:
https://xinyoudui.com/ac/contest/7470110AC000BED0906A0F/problem/13434
凸包面积

如图可知,一个多边形可以分成很多个三角形。
如何快速求出三个顶点坐标已知的三角形的面积?
考虑叉积计算的本质。


所以将->AB * ->AC /2=ABC三个点构成的三角形面积
全部评论 1
为何使用这么多 AI 截图
2026-07-14 来自 浙江
0哦我的问题,没看仔细
2026-07-14 来自 浙江
0



















有帮助,赞一个