【计算几何】二维凸包-Andrew算法

Andrew算法

• 将所有点排序，x为第一关键字，y为第二关键字
• 从左到右维护上半部分，从右至左维护下半部分
• 栈顶反向延长线的顺时针方向就留下，反之删除栈顶

double andrew(){
    sort(q,q+n);
    int top = 0;
    for (int i = 0;i < n;++i){
        while (top >= 2 && area(q[stk[top - 1]],q[stk[top]],q[i]) <= 0){
            if (area(q[stk[top - 1]],q[stk[top]],q[i]) < 0)
                used[stk[top--]] = 0;
            else
                top--;
        }
        stk[++top] = i;
        used[i] = 1;
    }
    used[0] = 0;
    for (int i = n-1;i >= 0;--i){
        if (used[i])    continue;
        while (top >= 2 && area(q[stk[top - 1]],q[stk[top]],q[i]) <= 0)
            top--;
        stk[++top] = i;
    }
}