Andrew算法凸包

admin1

[code]struct Point {
    double x, y;
    Point(double x = 0, double y = 0):x(x),y(y){}
};
typedef Point Vector;
Vector operator - (Point A, Point B){
    return Vector(A.x-B.x, A.y-B.y);
}
bool operator < (const Point& a, const Point& b){
    if(a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}
double Cross(Vector v0, Vector v1) {
    return v0.x*v1.y - v1.x*v0.y;
}
//计算凸包，输入点数组为 p，个数为 n， 输出点数组为 ch。函数返回凸包顶点数
//如果不希望凸包的边上有输入点，则把两个 <= 改为 <
//在精度要求高时建议用dcmp比较
//输入不能有重复点，函数执行完后输入点的顺序被破坏
int ConvexHull(Point* p, int n, Point* ch) {
    sort(p, p+n);
    int m = 0;
    for(int i = 0; i < n; ++i) {
        while(m > 1 && Cross(ch[m-1] - ch[m-2], p[i] - ch[m-2]) < 0) {
            m--;
        }
        ch[m++] = p[i];
    }
    int k = m;
    for(int i = n-2; i>= 0; --i) {
        while(m > k && Cross(ch[m-1] - ch[m-2], p[i] - ch[m-2]) < 0) {
            m--;
        }
        ch[m++] = p[i];
    }
    if(n > 1)
        --m;
    return m;
}
[/code]