平面凸包:为了包含几个元素,由最外面的元素连接形成的最小凸多边形
斜率逼近法:
1.寻找y值最小的点,从水平方向开始,逆时针旋转寻找第一个k>0且k最小的点
(ps:若有多个点符合目标要求,则选取最远的点,保证划定面积最大)
2.一直找到p1=pm为止
pps:平面凸包必然存在
方法漏洞:若k趋向于无穷则该题无解
Jarvis算法
不严谨的数学描述:一条直线过一点A,使得其他所有点在直线同一侧,然后顺时针或逆时针抡这根棍子,直到抡到除A以外的一点B。
遇到多个点一定要选取离A最远的点
方法漏洞:由于人为设置可以导致时间复杂度爆炸
Graham算法
求极角:
atan2(a[i].y,a[i].x)
选择y值最小,若y值相同则选择x值最小的点,按照极角大小进行排序
连接时若现左拐再右拐则出栈