在一个实数向量空间V中，对于给定集合X，所有包含X的凸集的交集S被称为X的凸包。

前置知识

叉积(Cross product): 用于计算角度，a x b =

* sinθ

极角排序: 在平面内取一个定点O，叫极点，引一条射线Ox，叫做极轴，再选定一个长度单位和角度的正方向（通常取逆时针方向）。对于平面内任何一点M，用ρ表示线段OM的长度（有时也用r表示），θ表示从Ox到OM的角度，ρ叫做点M的极径，θ叫做点M的极角，有序数对 (ρ,θ)就叫点M的极坐标。那么给定平面上的一些点，把它们按照一个选定的中心点排成顺（逆）时针。

Basic Code:

struct point {
    double x,y;
};
double cross(double x1,double y1,double x2,double y2){ //计算叉积
    return (x1*y2-x2*y1);
}
double count(point a,point b,point c) { //计算极角
    return cross((b.x-a.x),(b.y-a.y),(c.x-a.x),(c.y-a.y));
}

极角排序 —— atan2

关于atan2()函数：在C语言的math.h或C++中的cmath中有两个求反正切的函数atan(double x)与atan2(double y,double x) 他们返回的值是弧度要转化为角度再自己处理下。

前者接受的是一个正切值（直线的斜率）得到夹角，但是由于正切的规律性本可以有两个角度的但它却只返回一个，因为atan的值域是从-90~90 也就是它只处理一四象限，所以一般不用它。

第二个atan2(double y,double x) 其中y代表已知点的Y坐标，同理x ,返回值是此点与远点连线与x轴正方向的夹角，这样它就可以处理四个象限的任意情况了，它的值域相应的也就是-180~180了。

bool cmp1(point a,point b) {
    if(atan2(a.y,a.x)!=atan2(b.y,b.x))
        return atan2(a.y,a.x)<atan2(b.y,b.x);
    else return a.x<b.x;
}

极角排序 —— Cross Product

关于叉积：叉积=0是指两向量平行（重合）；叉积>0，则向量a在向量b的顺时针方向（粗略的理解为在a在b的下方）；叉积<0，则向量a在向量b的逆时针方向（粗略的理解为在a在b的上方）。

bool cmp2(point a,point b) {
    point c;//原点
    c.x = 0;
    c.y = 0;
    if(count(c,a,b)==0) return a.x<b.x;
    else return count(c,a,b)>0;
}

关于第一种方法，利用atan2排序，与利用叉积排序的主要区别在精度和时间上。

具体对比：时间：相较于计算叉积，利用atan2时间快，这个时间会快一点

Graham扫描法

静态凸包求解，时间复杂度：O（nlog(n)）

算法步骤：

首先先将最左下节点拿出，显然这个点一定是凸包结点，然后以这个点为极点，对点集作极角排序，角度一样的按照到极点距离从大到小排序，显然这时候最后一个节点，极点，第一个节点都会在凸包内
将排序后的前两个点入栈，其中栈中保存着凸包结点
构建凸包的过程可以总结为将栈顶和栈顶上一位元素所构成的向量与当前遍历的点和栈顶上一位元素所构成的向量作叉积，如果叉积大于等于0，就将当前遍历节点入栈，否则如果小于0，弹出栈顶，遍历节点入栈
直到我们遍历到节点为一开始排序的最后一个节点，节点入栈，程序结束，此时凸包结果就在栈中

Code

#include<bits/stdc++.h>
#define bug(a) (cout<<'*'<<a<<endl)
#define bugg(a,b) (cout<<'*'<<a<<' '<<b<<endl)
#define buggg(a,b,c) (cout<<'*'<<a<<' '<<b<<' '<<c<<endl)
using namespace std;
typedef long long ll;
struct point
{
	double x, y;
	double pos;
	point operator+(point a) { return point{ x + a.x,y + a.y }; }
	point operator-(point a) { return point{ x - a.x,y - a.y }; }
	double operator*(point a) { return  x *a.x+y * a.y; }
	point operator*(ll num) { return point{ x * num,y * num }; }
	double operator^(point a) { return x * a.y - y * a.x; }
};
point p[100009];
bool cmp(point a, point b)
{
	if (a.x != b.x && a.y != b.y)
		return a.pos < b.pos;
	else
		if (a.x == b.x)
			return a.y > b.y;
		else
			return a.x > b.x;
}
double dis(point a, point b)
{
	return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
int st[100009];
int main()
{
	int n, i, j;
	cin >> n;
	for (i = 1; i <= n; i++)
	{
		cin >> p[i].x >> p[i].y;
	}
	for (i = 1; i <= n; i++)
	{
		if (p[1].x > p[i].x || (p[1].x == p[i].x && p[1].y > p[i].y))
			swap(p[i], p[1]);
	}
	double x=p[1].x, y=p[1].y;
	for (i = 1; i <= n; i++)
	{
		p[i].x -= x;
		p[i].y -= y;
		p[i].pos = atan2(p[i].x, p[i].y);
	}
	sort(p + 2, p + 1 + n, cmp);
	int top = 0;
	st[++top] = 1, st[++top] = 2;
	for (i = 3; i <= n; i++)
	{
		while ((((p[st[top]] - p[st[top - 1]]) ^ (p[i] - p[st[top - 1]])) > 0) && top > 2)
			top--;
		st[++top] = i;
	}
	st[++top] = st[1];
	double ans = 0;
	for (i = 1; i <= top; i++)
	{
		ans += dis(p[st[i]], p[st[i - 1]]);
	}
	printf("%.2lf\n", ans);
	return 0;
}

模版题

https://www.luogu.com.cn/problem/P2742

凸包 —— Convex Hull