计算几何之凸包

凸包：把给定点包围在内部的、面积最小的凸多边形。

Andrew算法是Graham算法的变种，速度更快稳定性也更好。

首先把所有点排序，按照第一关键字x第二关键字y从小到大排序，删除重复点后得到点序列P1...Pn。

1)把P1,P2放入凸包中，凸包中的点使用栈存储

2)从p3开始，当下一个点在凸包当前前进方向（即直线p1p2）左边的时候继续；

3)否则依次删除最近加入凸包的点，直到新点在左边。

如图，新点P18在当前前进方向P10P15的右边（使用叉积判断），因此需要从凸包上删除点P15和P10，让P8的下一个点为P18。重复该过程直到碰到最右边的Pn，求出下凸包即凸包的下轮廓。然后从Pn反过来重复该步骤求出上凸包，合并起来后就是完整的凸包。

该算法扫描为O(n)复杂度，排序O(nlogn)。

具体可以参考刘汝佳的蓝书，有很好的讲解

来一道模板题

https://www.luogu.org/problemnew/show/P2742

一波代码：

 1 #pragma GCC optimize(2)
 2 #include<cstdio>
 3 #include<vector>
 4 #include<algorithm>
 5 #include<cmath>
 6 #define PI acos(double(-1))
 7 using namespace std;
 8 const int eps=1e-10;
 9 struct sd{
10     double x,y;
11     sd(){};
12     sd (double a,double b) {x=a,y=b;}
13     sd operator -(const sd v)const{return sd(x-v.x,y-v.y);}
14 }map[100005],stackk[100005];
15 int n;
16 double dis(sd a,sd b)
17 {
18     return sqrt((a.x-b.x)*(a.x-b.x)*1.0+(a.y-b.y)*(a.y-b.y)*1.0);
19 }
20 bool cmp(sd a,sd b)
21 {
22     if(a.x==b.x)
23     return a.y<b.y;
24     return a.x<b.x;
25 }
26 double fuck(sd a,sd b)
27 {
28     double ans=atan2((b.y-a.y),(b.x-a.x));
29     if(ans<-PI/2) ans=ans+PI*2;
30     return ans;
31 }
32 double cross(sd a,sd b)
33 {
34     return a.x*b.y-b.x*a.y;
35 }
36 int build()
37 {
38     int top=0;
39     sort(map,map+n,cmp);
40     for(int i=0;i<n;i++)
41     {
42         while(top>1&&cross(stackk[top-1]-stackk[top-2],map[i]-stackk[top-2])<=0) top--;
43         stackk[top++]=map[i];
44     }
45     int k=top;
46     for(int i=n-2;i>=0;i--)
47     {
48         while(top>k&&cross(stackk[top-1]-stackk[top-2],map[i]-stackk[top-2])<=0) top--;
49         stackk[top++]=map[i];
50     }
51     if(n>1) top--;
52     return top;
53 }
54 int main()
55 {
56     scanf("%d",&n);
57     for(int i=0;i<n;i++)
58     scanf("%lf%lf",&map[i].x,&map[i].y);
59     int top=build();
60     double ans=0;
61     for(int i=1;i<top;i++)
62     ans+=dis(stackk[i],stackk[i+1]);
63     ans+=dis(stackk[top],stackk[1]);
64     printf("%.2lf",ans);
65     return 0;
66 }