凸包【模板】

一看到凸包我是懵逼的，心想这是什么难度，我这种蒟蒻能学会么。 一看发现还是蛮简单的哈 我这里介绍常用的Graham扫描法，时间复杂度是nlogn 要学这种算法，先要知道一种叫叉积的东西 对于点A(x1,y1),B(x2,y2),C(x3,y3),向量AB与向量AC的叉积为(x2-x1)(y3-y1)-(x3-x1)(y2-y1),若叉积大于零，逆时针上两条边的夹角小于180°，反之则大于180°，等于零则共线。C在直线AB的逆时针方向，还是顺时针方向，简单来说，也就是在上面还是在下面。 根据常识，我们可以知道最左下角的点一定是凸包上的（你喜欢最左上，最右上。。也一样）。然后我们可以通过这个点去扩展出凸包，like this： 先加入点A、C  插入第三个点G  计算AC×CG的叉积，却发现叉积小于0，也就是说逆时针方向上∠ACG大于180度，于是删去C点，加入G点  同理，一步一步的做  那怎么找到点C呢？以A为原点，对其他点进行极角排序，也就是把A和其他点的连线按辐角排序。辐角是什么呢  就是这样，于是辐角最小的就是C点啦，用脚想想都知道C必定得选的，当然辐角最大的也必定得选。你可以从辐角最小的点逆时针扩展，当然也可以从辐角最大的点顺时针扩展。 程序详细步骤如下： 1.把所有点放在二维坐标系中，则纵坐标最小的点一定是凸包上的点 2.把所有点的坐标平移一下，使 A 作为原点 3.计算各个点相对于 A 的幅角 α ，按从小到大的顺序对各个点排序。当 α 相同时，距离 A 比较近的排在前面。我们由几何知识可以知道，结果中第一个点 B 和最后一个点一定是凸包上的点。 （以上是准备步骤，以下开始求凸包） 以上，我们已经知道了凸包上的第一个点 A 和第二个点 B，我们把它们放在栈里面。s[1]=A,s[2]=B.现在从步骤3求得的那个结果里，把 B 后面的那个点拿出来做当前点。此时栈顶指针top=2 4.连接s[top-1]和s[top]这两个点，得到直线 L 。看当前点是在直线 L 的右边还是左边。如果在直线的右边就执行步骤5；如果在直线上，或者在直线的左边就执行步骤6。 5.如果在右边，则s[top]不是凸包上的点，把栈顶元素出栈。执行步骤4。 6.当前点是凸包上的点，把它压入栈，执行步骤7。 7.检查当前点是不是步骤3那个结果的最后一个元素。是最后一个元素的话就结束。如果不是的话就把 P2 后面那个点做当前点，返回步骤4。 最后，栈中的元素就是凸包上的点了。 ------------ 程序如下 ```cpp #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n; struct node { int x,y; }p[50100],s[100100]; int cross(node a,node b,node c)//计算叉积 { return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y); } int dis(node a,node b) { return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y); } bool cmp1(node a,node b) { if(a.y==b.y) return a.x<b.x; return a.y<b.y; } bool cmp2(node a,node b)//极角排序 { int k=cross(s[1],a,b); if(k>0) return 1; else if(k==0 && dis(s[1],a)<=dis(s[1],b)) return 1;//共线的话就把距离近的排在前面 else return 0; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].y); sort(p+1,p+n+1,cmp1);//按横纵坐标排序，得出最左下角的点 s[1]=p[1]; sort(p+2,p+n+1,cmp2);//极角排序 s[2]=p[2];//得到辐角最小的点，入栈 int top=2; for(int i=3;i<=n;i++) { while(cross(s[top-1],s[top],p[i])<0) top--;//比较当前点在直线的右边还是左边。在右边就一直弹栈顶 s[++top]=p[i];//进栈 } for(int i=1;i<=top;i++) cout<<s[i].x<<" "<<s[i].y<<endl; return 0; } ```