围住奶牛问题

解题思路：

本题要求用一个围栏将所有点围住，要求围栏的周长最短，其实就是求这些点的凸包，凸包就是将所有点围住且周长最小的一个多边形。

这里直接套求二维凸包的模板即可，用的是 $Andrew$ 算法求二维凸包

注意，本题存在重复点，这可能导致一个点被用多次，因此可以在排序后再做一步去重。

C++ 代码

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<double, double> PDD;

const int N = 10010;

int n;
PDD q[N]; //存储所有点
int stk[N]; //存储凸包中所有的点
bool st[N]; //记录每个点是否在凸包上，防止复用

PDD operator- (PDD a, PDD b) //重载减号运算符
{
    return {a.x - b.x, a.y - b.y};
}

double cross(PDD a, PDD b) //求 a 和 b 的叉积
{
    return a.x * b.y - a.y * b.x;
}

double area(PDD a, PDD b, PDD c) //求 ab 和 ac 构成的平行四边形的有向面积
{
    return cross(b - a, c - a);
}

double get_dist(PDD a, PDD b) //求 a 和 b 之间的距离
{
    double x = a.x - b.x, y = a.y - b.y;
    return sqrt(x * x + y * y);
}

double andrew() //求二维凸包，并返回周长
{
    sort(q, q + n); //将所有点按照横纵坐标从小到大排序
    n = unique(q, q + n) - q; //去掉重复点

    int top = 0;
    for(int i = 0; i < n; i++) //求上凸包
    {
        while(top >= 2 && area(q[stk[top - 1]], q[stk[top]], q[i]) > 0) st[stk[top--]] = false;
        stk[++top] = i;
        st[i] = true;
    }

    st[0] = false;
    for(int i = n - 1; i >= 0; i--) //求下凸包
    {
        if(st[i]) continue;
        while(top >= 2 && area(q[stk[top - 1]], q[stk[top]], q[i]) > 0) top--;
        stk[++top] = i;
    }

    //统计凸包的周长
    double res = 0;
    for(int i = 2; i <= top; i++) res += get_dist(q[stk[i - 1]], q[stk[i]]);
    return res;
}

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%lf%lf", &q[i].x, &q[i].y);

    double res = andrew(); //andrew 算法求二维凸包，并返回周长
    printf("%.2lf\n", res);

    return 0;
}