graham算法C++代码

以下是Graham扫描法的C++代码实现：

#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;

struct Point {
    int x, y;
};

// 求两点之间的距离
double dist(Point a, Point b) {
    return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}

// 计算叉积
int crossProduct(Point a, Point b, Point c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

// 按极角排序
bool cmp(Point a, Point b) {
    int cp = crossProduct(p[0], a, b);
    if (cp > 0) {
        return true;
    } else if (cp == 0 && dist(p[0], a) < dist(p[0], b)) {
        return true;
    }
    return false;
}

int main() {
    int n;
    cin >> n;
    Point p[n];
    for (int i = 0; i < n; i++) {
        cin >> p[i].x >> p[i].y;
        if (p[i].y < p[0].y || (p[i].y == p[0].y && p[i].x < p[0].x)) {
            swap(p[i], p[0]);
        }
    }
    sort(p + 1, p + n, cmp);
    stack<Point> s;
    s.push(p[0]);
    s.push(p[1]);
    for (int i = 2; i < n; i++) {
        while (s.size() >= 2) {
            Point p2 = s.top(); s.pop();
            Point p1 = s.top(); s.pop();
            if (crossProduct(p1, p2, p[i]) > 0) {
                s.push(p1);
                s.push(p2);
                break;
            } else {
                s.push(p1);
            }
        }
        s.push(p[i]);
    }
    cout << s.size() << endl;
    return 0;
}

注：以上代码中的 `p` 数组是一个全局数组，用来保存所有的输入点。