计算几何 —— 二维凸包(1)

Andrew算法，稳定并且代码简单，建立手动栈，分上下凸包去构建，时间复杂度O(nlogn)。
以下以P2742 圈奶牛为例，代码如下：

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<iomanip>
using namespace std;

struct vec {
    double x, y;
} p[100005], st[100005];

bool cmp(vec a, vec b) {
    return a.x == b.x ? a.y < b.y : a.x < b.x;
}

double cross(vec a, vec b) {
    return a.x * b.y - a.y * b.x;
}

double side(vec A, vec B, vec C) {
    vec l1 = {B.x - A.x, B.y - A.y};
    vec l2 = {C.x - A.x, C.y - A.y};
    return cross(l1, l2);
}

double dis(vec a, vec b) {
    return sqrt((b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y));
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> p[i].x >> p[i].y;
    if (n == 1) {
        cout << fixed << setprecision(2) << 0.00;
        return 0;
    }
    sort(p + 1, p + n + 1, cmp);
    int top = 0;
    for (int i = 1; i <= n; ++i) {
        while (top > 1 && side(st[top - 1], st[top], p[i]) <= 0) {
            top--;
        }
        st[++top] = p[i];
    }
    int temp = top;
    for (int i = n - 1; i >= 1; --i) {
        while (top > temp && side(st[top - 1], st[top], p[i]) <= 0) {
            top--;
        }
        st[++top] = p[i];
    }
    double ans = 0;
    for (int i = 2; i <= top; ++i) {
        ans += dis(st[i], st[i - 1]);
    }
    cout << fixed << setprecision(2) << ans;
}