andrew算法求凸包

模板：

//判断大小注意精度，容易被卡
struct point{
    double x,y;
    bool operator < (point a){
        if(dcmp(x, a.x)) return dcmp(x, a.x) < 0;
        return dcmp(y, a.y) < 0;
    }
    bool operator == (point a) { return !dcmp(x, a.x) && !dcmp(y, a.y); }
};


point P[N];
int sta[N];
int andrew(int n)
{
    sort(P, P + n);
    n = unique(P, P + n) - P;
    int m = 0;
    for(int i=0; i<n; i++)      //先求下凸包
    {
        while(m > 1 && sign(area(P[sta[m - 2]], P[sta[m - 1]], P[i])) <= 0) m--;
        sta[m++] = i;
    }
    int v = m;
    for(int i=n - 2; i>=0; i--) //再求上凸包
    {
        while(m > v && sign(area(P[sta[m - 2]], P[sta[m - 1]], P[i])) <= 0) m--;
        sta[m++] = i;
    }
	if(n > 1) m--;              // 删去末尾多余的起始点，最后凸包是闭合的
    return m;
}

• PS：凸包（convex hall）和凸多边形（convex polygon）是不一样的，凸包有可能退化为线段，后者是前者的子集。