首先，求极角需要注意，
为了方便，当atan2值小于0时，atan2值加上2π作为极角大小，这样做对于下面的做法来说是比较方便的 

1
2
3
4
5
6
7
inline double atan3(double a,double b ){
    double t=atan2(a,b);
    if(t<0){
        t+=2*M_PI;
    }
    return t;
}
  1. 选取最下方的最左侧的点作为凸包初始点，将其他的点按照与这个点的连线极角大小进行排序。建议以极角作为第一关键字，距这个点的欧氏距离作为第二逆序关键字，这样我们会减轻接下来去重工作的负担。
  2. 按极角顺序遍历除初始点以外的所有点，若有极角相同的点，保留与初始点距离最大的那一个。由于1中我们有第二关键字，所以这里保留极角相同的第一个点即可。（注意如果是原址删除多余点的话，注意删除多余点之后点的顺序可能发生变化。其实这个问题和凸包本身没什么关系，只是自己手残写残，没有发现这个问题而已）
  3. 将初始点和极角最小的角压入凸包栈中。同时向偏角栈中压入0和极角最小角的极角（这个都压0也可以）
  4. 按极角顺序遍历剩余的所有点，对他们进行以下操作：
    1. 循环进行这个操作计算当前点与凸包栈栈顶元素连线的极角大小，如果这个值小于偏角栈栈顶元素，说明凸包栈栈顶的点是多余的，因为沿凸包边逆时针走，每次都不会向右转，如果偏角先大后小，说明向右转了，我们就需要把向右转的点和它对应的偏角弹出。当这个操作不能进行后，继续。
    2. 将当前点和当前点与凸包栈栈顶元素连线的极角大小分别压入凸包栈和偏角栈中。
  5. 你已经得到了按顺序排列在凸包栈中的凸包边上的所有点了，凸包得求。

PS:

好像只有我一个人傻乎乎的用atan来求极角，别人都是用叉积来算的。