用不严谨的话来讲，给定二维平面上的点集，凸包就是将最外层的点连接起来构成凸多边形，它能包含点集中所有的点。
构造方法
需要牢记的是
若 \(a × b>0\) 则 \(a\) 在 \(b\) 的顺时针方向
若 \(a × b=0\) 则 \(a\) 与 \(b\) 共线
若 \(a × b>0\) 则 \(a\) 在 \(b\) 的逆时针方向
①极角排序
选择一个点作为基础点，进行极角排序。
可以通过比较叉积的方式进行极角排序，若叉积相同，则离基础点近的点优先级高。
Point Base;
bool cmp_ang(const Point &a,const Point &b)
{int tmp=dcmp(cross(a-Base,b-Base));if(tmp==0)return dist(Base,a)<dist(Base,b);else return tmp>0;
}②构造凸包
从左下逆时针构造凸包，若这样构造那么只需要判断，栈顶的点，与当前加入的点，和栈中第二个点构成的向量，那个更靠外侧（那个处于另一个的顺时针方向），若当前加入的点更优，就将之前的点出栈。
时间复杂度 \(O(n)\)
for(int i=1;i<=num;i++)
if(s[i]<s[1])swap(s[1],s[i]);
sort_point(s,2,num,s[1]);
cnt=2;
node[1]=s[1],node[2]=s[2];
for(int i=3;i<=num;i++)
{while(cnt>=2&&dcmp(cross(node[cnt]-node[cnt-1],s[i]-node[cnt-1]))<=0)cnt--;node[++cnt]=s[i];
}③判断一个多边形是否是凸包
方法一：根据多边形的点构造一个凸包，看是否与原多边形相等。
方法二：顺时针，或者逆时针检查每两条线段的叉积的正负情况，如果有正有负，则不是凸包。
bool is_convex_hull()
{bool s[3];memset(s,0,sizeof(s));for(int i=1;i<cnt-1;i++){s[dcmp(cross(node[i+1]-node[i],node[i+2]-node[i]))+1]=true;if(s[0]&&s[2])return false;}s[dcmp(cross(node[cnt-1]-node[cnt-2],node[cnt]-node[cnt-2]))+1]=true;s[dcmp(cross(node[cnt]-node[cnt-1],node[1]-node[cnt-1]))+1]=true;s[dcmp(cross(node[1]-node[cnt],node[2]-node[cnt]))+1]=true;if(s[0]&&s[2])return false;return true;
}④判断一个点是否在凸包内部
方法一（只适用于凸包）：判断点是否在凸包每个角的中间（运用叉积判断）。
方法二（适用于所有多边形）：引一条射线，判断射线与多边形交点个数，若为奇数个则，在多边形内部，否则在边上，或者外面。
int is_in_polygon(Point a)
{Line ray;//射线ray.s=a;ray.e=Vector(-100000000.0,a.y);int ans=0;for(int i=1;i<=cnt;i++){Point s1=edge[i].s,s2=edge[i].e;if(on_seg(a,edge[i]))return 0;//若a在边上返回0if(dcmp(s1.y-s2.y)==0)continue;//若平行无视这条边if(on_seg(s1,ray))//若上端点在射线上取上端点{if(dcmp(s1.y-s2.y)>0)ans++;}else if(on_seg(s2,ray))//同理{if(dcmp(s2.y-s1.y)>0)ans++;}else if(is_cross(ray,edge[i]))ans++;//判断线段与线段是否相交}if(ans%2==1)return 1;return -1;
}里面用到了两个函数现在给出它们的实现方法
判断点是否在线段上，首先判断点是否在直线上，然后判断点的左边范围，是否符合线段的条件
bool on_seg(Point a,Segment a1)
{Point b=a1.s,c=a1.e;return dcmp(cross(b-a,c-a))==0&&min(b.x,c.x)<=a.x&&a.x<=max(b.x,c.x)&&min(b.y,c.y)<=a.y&&a.y<=max(b.y,c.y);
}首先检查点的跨立情况，然后处理特殊情况（两条直线重合）
事实证明快速排斥，只是用来加快判断速度（对正确性并无影响）
如果说是规范相交去掉后面的四个判断（判断两条直线重合）
bool is_cross(Line a1,Line a2)
{Point a=a1.s,b=a1.e,c=a2.s,d=a2.e;int c1=dcmp(cross(b-a,c-a));int c2=dcmp(cross(b-a,d-a));int o1=dcmp(cross(d-c,b-c));int o2=dcmp(cross(d-c,a-c));if(c1*c2<=0&&o1*o2<=0)return true;if(c1==0&&on_seg(c,a1))return true;if(c2==0&&on_seg(d,a1))return true;if(o1==0&&on_seg(b,a2))return true;if(o2==0&&on_seg(a,a2))return true;return false;
}⑤判断圆是否在凸包内部
先判断圆心是否在凸包内部，然后判断圆心到凸包每条边的最近点的距离是否小于圆的半径。
bool circle_is_in_convex_hull(Circle a)
{if(is_in_polygon(a.O)<0)return false;for(int i=1;i<=cnt;i++)if(dcmp(dist(a.O,get_nearest_point_on_segment(a.O,edge[i]))+eps-a.R)<0)return false;return true;
}下面给出求点离线段的最近点的函数
求最近点有三种情况
最近点为左端点
最近点为右端点
最近点在线段中间
我们可以通过点乘，求出交点到左端点的距离，占线段总长度的比例。
dot(a-b,c-b)/dot(c-b,c-b)即为 \(a·b\) =\(cos\theta|a||b|/(|b|^2)=cos\theta|a|:|b|\)
\(cos\theta|a|\) 的意义不言而喻。
Point get_nearest_point_on_segment(Point a,Line a1)
{Point b=a1.s,c=a1.e;double t=dot(a-b,c-b)/dot(c-b,c-b);if(dcmp(t)!=-1&&dcmp(1-t)!=-1)return Vector(b.x+(c.x-b.x)*t,b.y+(c.y-b.y)*t);if(dist(a,b)<dist(a,c))return b;return c;
}⑥动态凸包
运用splay维护凸包（待填坑，若想了解，可以发表评论）