P2742 [USACO5.1]圈奶牛Fencing the Cows /【模板】二维凸包

Link

Solution

凸包模板题，根据给定点集画出凸包后把每条边加起来就是答案，使用了一波jls的几何模板

Code

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

using db = double;
const db eps = 1e-6;
const db PI = acos(-1);

int sign(db k)
{
    if (k > eps)
        return 1;
    else if (k < -eps)
        return -1;
    return 0;
}
int cmp(db k1, db k2) { return sign(k1 - k2); }

class Point {
public:
    db x, y;
    Point() = default;
    Point(db xx, db yy) : x(xx), y(yy) {}
    Point operator+(const Point &that) const
    {
        return {x + that.x, y + that.y};
    }
    Point operator-(const Point &that) const
    {
        return {x - that.x, y - that.y};
    }
    Point operator*(db k) const { return {x * k, y * k}; }
    Point operator/(db k) const { return {x / k, y / k}; }
    int operator==(const Point &rhs) const
    {
        return cmp(x, rhs.x) == 0 && cmp(y, rhs.y) == 0;
    }
    bool operator<(const Point rhs) const
    {
        int a = cmp(x, rhs.x);
        if (a == -1)
            return 1;
        else if (a == 1)
            return 0;
        else
            return cmp(y, rhs.y) == -1;
    }
    db abs() { return sqrt(x * x + y * y); }
    db dis(Point k1) { return ((*this) - k1).abs(); }
};

db cross(Point k1, Point k2) { return k1.x * k2.y - k1.y * k2.x; }

vector<Point> ConvexHull(vector<Point> A, int flag = 1)
{
    int n = A.size();
    vector<Point> ans(n * 2);
    sort(A.begin(), A.end());
    int now = -1;
    for (int i = 0; i < A.size(); i++) {
        while (now > 0 &&
            sign(cross(ans[now] - ans[now - 1], A[i] - ans[now - 1])) < flag)
            now--;
        ans[++now] = A[i];
    }
    int pre = now;
    for (int i = n - 2; i >= 0; i--) {
        while (now > pre &&
            sign(cross(ans[now] - ans[now - 1], A[i] - ans[now - 1])) < flag)
            now--;
        ans[++now] = A[i];
    }
    ans.resize(now);
    return ans;
}

int main()
{
    int n;
    double x, y;
    cin >> n;
    vector<Point> v;
    for (int i = 0; i < n; i++) {
        cin >> x >> y;
        v.push_back({x, y});
    }
    vector tmp = ConvexHull(v);
    double ans = 0;
    for (int i = 0; i < tmp.size(); i++) ans += tmp[i].dis(tmp[i + 1]);
    printf("%.2f\n", ans);
    return 0;
}