极角排序和Graham Scan法求凸包
极角排序
极角:向量和x轴正方向的形成的角。
Graham Scan法求凸包
凸包:凸包是把给定点包围在内部的、面积最小的凸多边形。
Scan法求凸包:在给定点集中找到y坐标最小的点,这个点一定是凸包上一点,那么所有点按照这个点极角排序,在凸包上的点满足这样的关系,即每个点都在凸包边的一侧。这样我们可以通过叉积,维护一个凸包集合不断进而求出凸包的集合。
时间复杂度:极角排序 O(nlogn),求凸包的过程是 O(n) 的,所以算法整体的复杂度为 O(nlogn)。
注意:对于凸包上共线的点,视情况舍取。
HDU1348 凸包模板题
1 |
|