题解 | #圈奶牛#

#include <stdio.h> #include <stdlib.h> #include <math.h>

typedef struct { double x, y; } Point;

Point points[10005]; Point hull[20010]; // 凸包顶点，大小设为2N以防最坏情况

int cmp(const void *a, const void *b) { Point *p1 = (Point *)a; Point *p2 = (Point *)b; if (p1->x != p2->x) return (p1->x > p2->x) ? 1 : -1; else return (p1->y > p2->y) ? 1 : -1; }

// 叉积：返回 (b-a) × (c-a) double cross(Point a, Point b, Point c) { return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x); }

// 计算两点间距离 double distance(Point a, Point b) { return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); }

double convexHull(int n) { if (n == 1) return 0.0; // 单点周长为0 if (n == 2) return 2 * distance(points[0], points[1]); // 两点围栏长度为两倍距离（题目要求围住）

qsort(points, n, sizeof(Point), cmp);

int k = 0;
// 构建下凸包
for (int i = 0; i < n; ++i) {
    while (k >= 2 && cross(hull[k-2], hull[k-1], points[i]) <= 0)
        k--;
    hull[k++] = points[i];
}
// 构建上凸包
for (int i = n-2, t = k+1; i >= 0; --i) {
    while (k >= t && cross(hull[k-2], hull[k-1], points[i]) <= 0)
        k--;
    hull[k++] = points[i];
}
k--; // 去除最后一个重复点（起点）

// 计算凸包周长
double perimeter = 0.0;
for (int i = 0; i < k; ++i) {
    perimeter += distance(hull[i], hull[(i+1)%k]);
}
return perimeter;

}

int main() { int N; scanf("%d", &N); for (int i = 0; i < N; ++i) { scanf("%lf %lf", &points[i].x, &points[i].y); } double ans = convexHull(N); printf("%.2f\n", ans); return 0; }