二维凸包模板(Graham算法)

矫情吗；* 2022-06-11 09:26 261阅读 0赞

时间复杂度O(nlogn)

模板：

#include <cstdio>
    #include <cmath>
    #include <cstdlib>
    #include <algorithm>
    #define eps 1e-8
    #define MAXN 110
    using namespace std;
    struct Point
    {
        double x, y;
        Point(){}
        Point(double X, double Y){
            x = X; y = Y;
        }
    };
    Point P[MAXN];
    int dcmp(double x)
    {
        if(fabs(x) < eps)
            return 0;
        else
            return x < 0 ? -1 : 1;
    }
    Point operator - (Point A, Point B){
        return Point(A.x-B.x, A.y-B.y);
    }
    Point operator + (Point A, Point B){
        return Point(A.x+B.x, A.y+B.y);
    }
    Point operator * (Point A, double p){
        return Point(A.x*p, A.y*p);;
    }
    double Cross(Point A, Point B){
        return A.x*B.y - A.y*B.x;
    }
    double Dot(Point A, Point B){
        return A.x*B.x + A.y*B.y;
    }
    double Dis(Point A, Point B){
        return sqrt((A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y));
    }
    bool operator == (Point A, Point B){
        return dcmp(A.x-B.x) == 0 && dcmp(A.y-B.y) == 0;
    }
    bool cmp(Point A, Point B)//按极角升序排序，若角度相等距离小的在前面
    {
        double temp = Cross(A-P[0], B-P[0]);
        if(dcmp(temp) > 0) return true;
        if(dcmp(temp) == 0 && dcmp(Dis(P[0], A) - Dis(P[0], B)) < 0) return true;
        return false;
    }
    int Stack[MAXN], top;//下标从0开始计数到top
    void input(int n)
    {
        scanf("%lf%lf", &P[0].x, &P[0].y);
        double xx = P[0].x, yy = P[0].y;
        int id = 0;//找到y坐标最小的点，若有多个选择x坐标最小的记录下标
        for(int i = 1; i < n; i++)
        {
            scanf("%lf%lf", &P[i].x, &P[i].y);
            if(P[i].y < yy || (P[i].y == yy && P[i].x < xx))
            {
                xx = P[i].x;
                yy = P[i].y;
                id = i;
            }
        }
        Point T;
        T = P[0]; P[0] = P[id]; P[id] = T;
        sort(P+1, P+n, cmp);//极角排序
    }
    void Graham(int n)
    {
        if(n == 1){ top = 0; Stack[0] = 0;}
        else if(n == 2)
        {
            top = 1;
            Stack[0] = 0;
            Stack[1] = 1;
        }
        else
        {
            for(int i = 0; i <= 1; i++)
                Stack[i] = i;
            top = 1;
            for(int i = 2; i < n; i++)
            {   //如果和上一条边成左旋关系，压栈继续；反之一直弹栈直到和栈顶两点的边成左转关系，压栈继续。
                while(top > 0 && dcmp(Cross(P[Stack[top]]-P[Stack[top-1]], P[i]-P[Stack[top-1]])) <= 0) top--;
                top++;
                Stack[top] = i;
            }
        }
    }
    int main()
    {
        int n;
        input(n);
        Graham(n);
        return 0;
    }