数论小白都能看懂的平面凸包详解

### 注：这原本是一篇日报，但由于没通过一怒之下交成题解（大雾 # 0.前言： 本篇文章，是一位 OI 选手无私的馈赠。两道凸包例题，五种凸包算法，涵盖了平面凸包从入门到进阶的大部分套路。作者相信，这篇漂亮的博客，可以给拼搏于 OI 的逐梦之路上的你，提供一个有力的援助。 ## 特别鸣谢： - 画图：主要提供比较细的连线 - 画图3D：主要提供描点及文本框 杜绝网上搜图，图片纯手画~~累死我了~~ # 1.引入： 假设一个操场上有一些小朋友，下面是航拍视角：  现在他们要围一个球场做游戏。 因为老师比较懒，所以就只能麻烦一些小朋友了（他们自己撑着绳子防止球滚出去） 而小朋友又不动脑子。所以就只能麻烦你来出主意了。 显然，最简单的方法是这样：  先把一圈大绳子放在外面，然后往里缩，直到：  最外圈的小朋友撑起了绳子。 此时黑线围成的多边形的顶点就是最外圈小朋友所在的位置。 ### 由此，**我们就定义黑线围成的图形为一个平面凸包** 那么，换一种定义方式，我们就定义： **平面凸包是指覆盖平面上n个点的最小的凸多边形。** 当然，我们发现在程序中却无法模拟此过程，于是有了下文的诞生。 # 2、斜率逼近法 **其实这也是一种容易想到的算法，但是并不常用（代码复杂度高），我们稍作了解** 然后我们可以把这个思路具体化：   （k是斜率） - (1)首先在所有点中找出一个y值最小的点，记为$P_1$ - (2)从$P_1$出发，刚开始k=0，即为水平状态。然后按照上图的示意沿逆时针方向寻找。即开始在$k>0$且$(x_2>x1,y_2>y_1)$中找k最小的点$P_2$，以此类推。 Q:如果过程中有多个点符合要求怎么办？ A:那么就取距离$P_1$最远的点，因为这样能保证划定的范围最大。 - （3）从$P_2$出发，用（2）的方法找$P_3$ - (4)最后直到$P_m=P_1$为止（已形成凸包）。 Q:为什么要刚开始找y值最小的点？ A:结合刚开始的小朋友拉绳子可知，我们在下面的绳子一定会被y值最小的小朋友挡住，即他一定在凸包上，于是就以他为基准来操作。 Q:万一最后没有一个$P_m$使得$P_m=P_1$呢？ A:易证必有，平面凸包总是存在的。 **时间复杂度：O(nm)** n为所有小朋友的数量，m为舍己为人的小朋友的数量。 说到这里大家都明白了，一但凸包上的两个点的斜率趋于无穷大，那么就无法解决了。 于是~~窝的日报又能进行下去了~~有人就提出了一种新的方法。 # 3、Jarvis算法 这其实是一种数学构造法 我们还是把那群小朋友~~骗~~聘过来：  我们考虑让一个小朋友手里拿着一根棒子：  从外往里旋转。 然后会~~撂倒~~碰到另一个小朋友：  然后我们让被棒子碰到的小朋友再取一根棒子~~继续打人~~，重复以上操作。  就是这样。 但如果遇到以下情况：  有的小朋友在旋转棍子时同时碰到了多于一个点（即三点共线），那么显然我们需要选择最远的点。 不难证明，这样下来也可以围成一个平面凸包。 **以上是定向的想象，那么下面就来严谨的说明一下** 描述如下：  - 首先找到一条直线$l$过其中一点A，使得所有其他的点都在$l$的同一侧。 这种直线显然一定能找到。 由此也易证A一定为凸包上一点。 - 让直线$l$以A为轴点沿顺时针或逆时针方向旋转，直到抡到除A以外的一点B 别忘了上面那个~~形象的~~讲述，在遇到多于一个点时要取最远的。 - 重复以上操作，直到l碰到A点。 在过程中~~受伤~~被碰到的点就构成了平面凸包的顶点序列。 **在此过程中，虽然我们发现上述过程仍然不太好实现，但是我们还是可以通过一系列的玄学转换得到** 我们考虑到B点是最先碰到的，那么新的直线$l'$必然在A和除B及自身以外其他点的连线中与$l$的夹角最小  即紫∠比红∠大 那么在下图中：  $if(\vec {AP}\times \vec {AP_i})z>0$ 则$\vec {AP}$到$\vec {AP_i}$的旋转为逆时针旋转。 显然，$\vec {AP_i}$与l的夹角比$\vec {AP}$的更接近。为更好的答案。 $else$ $if(\vec {AP}\times \vec {AP_i})z=0$ 那说明A，P，$P_i$三点共线，自然取最远的。 我们按这个顺序扫描所有的点，就能找到这个凸包上的一条边。 显而易见：此时间复杂度为$O(nm)$，即每次扫n个点，一共m次可构成凸包。 但是。。。这个时间复杂度还是会凉。。。 假设就是[这道题](https://www.luogu.org/problem/P2742),那么我们观察到$n\leq 10000$,这是一道平面凸包的模板题，但是如果数据构造到m=n甚至和n相差不大的情况，那就会轻而易举的超时。 可见，此算法仅仅适用于随机点集，对于刻意构造的数据就会被卡成$O(n^2)$ 而毒瘤的OI怎么会不卡呢？ **连模板题都过不了，看来这个算法还是得优化，所以我们还是得用保险的算法，于是** # 4、Graham算法 本质： > Graham扫描算法维护一个**凸壳** 通过不断在**凸壳**中加入新的点和去除影响凸性的点 最后形成**凸包** **至于凸壳：** 就是凸包的一部分 算法主要由两部分构成： - 排序 - 扫描 ## （1）排序 我们的Graham算法的第一步就是对点集进行排序，这样能保证其有序性，从而在后续的处理中达到更高效的效果，这也是Graham算法更优的原因。 开始操作： - 我们还是选择一个y值最小（如有相同选x最小）的点，记为$P_1$ - 剩下的点集中按照极角的大小逆时针排序，然后编号为$P_2$~$P_m$  ~~达成成就：种草达人~~ **另外再介绍一个求极角的黑科技：atan2(a[i].y,a[i].x)** - 我们按照排序结束时的顺序枚举每一个点，依次连线，这里可以使用一个栈来存储，每次入栈，如果即将入栈的元素与栈顶两个元素所构成了一个类似于凹壳的东西，那么显然处于顶点的那个点一定不在这个点集的凸包上，而他正好在栈顶，所以把它弹出栈，新点入栈。 但是，新来的点有可能既踢走了栈顶，再连接新的栈顶元素后却发现仍然可以踢出，此时就不能忘记判断。 **怎么样，感觉这个算法如何？** 如果您不想纠缠于繁杂的文字描述，那么下面就有精美图片解说献上。 （ps:下列解说中右转左转等是指以上一条连线为铅垂线，新的连线偏移的方位） --- 刚开始，我们的点集是这样的：  其中p1为起始点 --- 然后p2准备入栈，由于栈中元素过少，所以检验合格，可直接进入。  ---- 之后因为p3仍为向左转，符合凸包条件，所以暂时先让它进去  --- p4出现了右转现象，那么我们就把顶点p3舍去，在检查p2的性质，合格 于是p3出栈，p4入栈  --- p5一切正常，入栈。  ---- p6这里就要复杂一些 - 首先他往右转，于是将p5弹出  - 又发现他相对于$P_2P_4$向右转，于是将p4弹出  之后p6进栈。 ---- p7一切正常（左转），入栈  ---- p8一切正常（左转），入栈  --- 所以说最后就连到了起点p1。  由此，我们的Graham算法的全过程就结束了。 凸包形成（即绿线所围的多边形） 扫描的时间复杂度：$O(n)$ 但是显然不可能做到这么优秀. 于是还有排序的时间复杂度：$O(nlogn)$ 合起来总的时间复杂度：$O(nlogn)$ **可见，我们在排序的帮助下省去了一些盲目的扫描，虽然排序作为一个预处理时间复杂度占据了总时间复杂度，但相比前一个算法还是更为优秀** 现在我们到模板题上来。 [P2742 【模板】二维凸包 / [USACO5.1]圈奶牛Fencing the Cows](https://www.luogu.org/problem/P2742) ### 题意简叙： 求一个点集凸包的边长和。 ### 分析： 平面凸包模板题，注意浮点数之类的别弄丢精度就行，其他直接套模板,代码里有注释，我用的是手写栈，（这样能快一些？ ### code： ```cpp #include<iostream> #include<algorithm> #include<cstdio> #include<cmath> using namespace std; int n; struct ben { double x,y; }p[10005],s[10005]; double check(ben a1,ben a2,ben b1,ben b2)//检查叉积是否大于0，如果是a就逆时针转到b { return (a2.x-a1.x)*(b2.y-b1.y)-(b2.x-b1.x)*(a2.y-a1.y); } double d(ben p1,ben p2)//两点间距离。。。 { return sqrt((p2.y-p1.y)*(p2.y-p1.y)+(p2.x-p1.x)*(p2.x-p1.x)); } bool cmp(ben p1,ben p2)//排序函数，这个函数别写错了，要不然功亏一篑 { double tmp=check(p[1],p1,p[1],p2); if(tmp>0) return 1; if(tmp==0&&d(p[0],p1)<d(p[0],p2)) return 1; return 0; } int main() { scanf("%d",&n); double mid; for(int i=1;i<=n;i++) { scanf("%lf%lf",&p[i].x,&p[i].y); if(i!=1&&p[i].y<p[1].y)//这是是去重 { mid=p[1].y;p[1].y=p[i].y;p[i].y=mid; mid=p[1].x;p[1].x=p[i].x;p[i].x=mid; } } sort(p+2,p+1+n,cmp);//系统快排 s[1]=p[1];//最低点一定在凸包里 int cnt=1; for(int i=2;i<=n;i++) { while(cnt>1&&check(s[cnt-1],s[cnt],s[cnt],p[i])<=0) //判断前面的会不会被踢走，如果被踢走那么出栈 cnt--; cnt++; s[cnt]=p[i]; } s[cnt+1]=p[1];//最后一个点回到凸包起点 double ans=0; for(int i=1;i<=cnt;i++) ans+=d(s[i],s[i+1]);//然后s里存好了凸包序列，只需要把两两距离累加就行 printf("%.2lf\n",ans); return 0; } ``` # 4、例题： ## 信用卡凸包 [P3829 [SHOI2012]信用卡凸包](https://www.luogu.org/problem/P3829) 是一道上海的省选题，不过并不难。 ### 题意简叙：  给你一堆如上图所示的卡片，求其凸包周长（凸包可以包含圆弧） ### 分析： 我们可以先来考虑$r=0$的情况。 发现$r=0$即为信用卡为矩形，于是就按照正常的思路将点列出跑Graham算法即可。 --- 然后开始想正解 因为样例三是最普遍的情况，所以研究一下：  首先带有圆弧的凸包不好处理呢。 于是我们把每一个被磨圆的顶角往圆心里看，再重新构造凸包，然后发现黑色内圈与绿蓝外圈有重叠部分。 再分解一下，如红笔。 **发现恰好多出4个$\frac{1}{4}$圆弧，也就是一个圆** 再验证几个发现也是对的。 于是这个问题就转换为裸的凸包模板了。 #### 这种题目里面都告诉凸包了，关键在于怎么转换，不然生搬硬套，很难得分 # 5、Andrew算法 （评论区里一个大连提出了这个补充，于是添加一下QAQ） ### 主体思路： - 按照x优先的顺序排序（坐标从小到大） - 从第一个点开始遍历，如果下一个点在栈顶的两个元素所连成直线的左边，那么就入栈； - 否则如果在右边，说明凸包有更优的方案，上次的点出栈，并直到新点在栈顶两个点所在的直线的左边为止 显然文字解释仍然是枯燥的，那么下面还是手动绘图感受一下~~我的妈呀累死我了~~ --- 以下就是两种算法的排序不同  我来分割一下--------------------------------------------------------------------------------------------------------  可以看出两种算法的排序不同，Andrew算法排序更简单，按x，y坐标排序，时间复杂度也更低（一般的坐标系中排序方法）。 --- 第一步：将前两个点入栈 - 首先p1一定是在凸包顶点上的。 - p2可能在，也可能不在，等着之后判断 ~~为了我也不知道什么原因我把黑的坐标轴给去掉了~~  --- p3偏左，入栈  --- p4和p3连线，发现偏右，于是p3出栈，检查p2正常，于是p4再入栈  --- 和上面的同理； 于是p4出栈，p5入栈  --- p5出栈，p6出栈  --- p6出栈，p7入栈  --- p8一马平川的入栈  --- ### 然后我们惊讶的发现： 凸包明明还空一半就到头了。  **然鹅这其实是在意料之中的** 我们这种算法必然会只算出一半的凸包。 - 如果你按照本文的方法行动，那就是一个下凸包 然后上凸包我想你已经知道怎么处理了 ### 那下面就揭晓答案： 我们再从排序末尾的点（也就是p8）出发，按照一模一样的方式再往前遍历就行。 如图。 从8~1走。 当然走过的节点就没有必要再走了（除了p1） - 先走到p6  --- 再到p5，发现我们可以把p6给踢掉了。 - p6出栈，p5入栈  --- 然后p5到p4 - 这里可能画的不是很清楚，其实是不共线的 - 如果共线也好处理，直接取最长的哇  --- 出现了p3！！！ - 他首先把p4给请出去了  --- - 然后又把p5给请出去了  总结：p4，p5出栈，p3入栈 --- 最后p3连到p1，画上了一个圆满的~~句号~~凸包  ### 以上就是Andrew算法全过程QAQ 扫描的时间复杂度：$O(n)$（已过滤常数） 排序时间复杂度：$O(nlogn)$ #### 总时间复杂度：$O(nlogn)$ ## code: ```cpp double Cross(vec A, vec B) { return A.x*B.y-A.y*B.x; //A->B左转为正 } double Side(vec a, vec b, vec p) //次栈顶元素a，栈顶元素b，新增点p { vec A=vec(b.x-a.x,b.y-a.y); //向量ab vec B=vec(p.x-a.x,p.y-a.y); //向量ap return Cross(A,B); } int Andrew(int top) { sort(p+1,p+n+1); if(n<3) { printf("-1\n"); return; } st[0]=p[1],st[1]=p[2]; top=1; for (int i=3;i<=n;i++)//从p1开始的下凸包 { while(top&&Side(st[top-1],st[top],p[i])<=0) top--; st[++top]=p[i]; } st[++top]=p[n-1]; for(int i=n-2;i>=1;i--)//从pn开始的上凸包 { while(top&&Side(st[top-1],st[top],p[i])<=0) top--; st[++top]=p[i]; } return top; } ``` # 6、后记： 不管怎样，这一篇日报居然写完了，虽然这种算法考察在noip中不常见，但最近风云变幻，谁知道以后会出什么题，但现在把整个算法的各种变形都推得明明白白还不如复习好之前的算法，所以我们到目前把模板掌握，避免考试出板子时却手足无措的情况发生就行。 - 配图十分不易，讲解努力详细，望您不吝赐赞