凸包问题

2024-08-14

采用Andrew算法求解计算几何中的二维凸包问题

#include <bits/stdc++.h>
#define io cin.tie(0), cout.tie(0), ios::sync_with_stdio(false)
#define LL long long
#define ULL unsigned long long
#define EPS 1e-6
#define INF 0x7fffffff
#define SUB -INF - 1
using namespace std;
const int N = 100001;
int sgn(double x)
{
    if (fabs(x) < EPS)
        return 0;
    else
        return x < 0 ? -1 : 1;
}
struct Point
{
    double x, y;
    Point() {}
    Point(double x, double y) : x(x), y(y) {}
    Point operator+(Point B) { return Point(x + B.x, y + B.y); }
    Point operator-(Point B) { return Point(x - B.x, y - B.y); }
    bool operator==(Point B) { return sgn(x - B.x) == 0 && sgn(y - B.y) == 0; }
    bool operator<(Point B) { return sgn(x - B.x) < 0 || (sgn(x - B.x) == 0 && sgn(y - B.y) < 0); }
};
typedef Point Vector;
double Cross(Vector A, Vector B) { return A.x * B.y - A.y * B.x; }
double Distance(Point A, Point B) { return hypot(A.x - B.x, A.y - B.y); }
int Convex_hull(Point *p, int n, Point *ch)
{
    n = unique(p, p + n) - p;
    sort(p, p + n);
    int v = 0;
    for (int i = 0; i < n; i++)
    {
        while (v > 1 && sgn(Cross(ch[v - 1] - ch[v - 2], p[i] - ch[v - 1])) <= 0)
            v--;
        ch[v++] = p[i];
    }
    int j = v;
    for (int i = n - 2; i >= 0; i--)
    {
        while (v > j && sgn(Cross(ch[v - 1] - ch[v - 2], p[i] - ch[v - 1])) <= 0)
            v--;
        ch[v++] = p[i];
    }
    if (n > 1)
        v--;
    return v;
}
Point p[N], ch[N];
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        scanf("%lf%lf", &p[i].x, &p[i].y);
    int v = Convex_hull(p, n, ch);
    double ans = 0;
    for (int i = 0; i < v; i++)
        ans += Distance(ch[i], ch[(i + 1) % v]);
    printf("%.2lf\n", ans);
    return 0;
}