算法标签：

计算几何 凸包

题解

本题是要为多边形城堡建围墙，要求围墙距城堡至少 (L) 英尺且长度最短。这是典型的几何凸包问题，因最短围墙围绕在凸包外侧。

代码中，先定义 point 结构体存储点坐标。find_pole_point 函数遍历顶点找基点（(y) 最小，(y) 相同则 (x) 最小）并与首元素交换。dis 函数用两点间距离公式算距离，cross 函数计算向量叉积判断点相对位置。cmp 函数以基点为参照，依叉积和距离对点排序。scanner 函数先找基点、排序，再遍历排序点集，用叉积判断是否删凸包栈顶元素来构建凸包。主函数读取顶点数 (m)、距离 (L) 和顶点坐标，调用 scanner 求凸包，计算时先加圆角外扩长度 (2\pi L) ，再累加凸包边长，最后四舍五入输出。时间复杂度主要由排序决定，为 (O(m log m)) 。

#include <iostream>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;

int m, top;
struct point {
    int x, y;
} P[2000], S[2000], T;

void find_pole_point() { //找到基点 交换到 0 
    int i, j = 0;
    T = P[0];
    for (i = 1; i < m; i++) {
        if (P[i].y < T.y || (P[i].y == T.y && P[i].x < T.x)) {
            j = i;
            T = P[i];
        }
    }
    T = P[0];
    P[0] = P[j];
    P[j] = T;
}

double dis(point t1, point t2) { //计算两点距离
    double z = (t1.x - t2.x) * (t1.x - t2.x) + (t1.y - t2.y) * (t1.y - t2.y);
    return sqrt(z);
}

double cross(point t1, point t2, point t3, point t4) { //向量叉积
    return (t2.x - t1.x) * (t4.y - t3.y) - (t2.y - t1.y) * (t4.x - t3.x);
}

bool cmp(point t1, point t2) {
    double z = cross(P[0], t1, P[0], t2);
    return z? z > 0 : dis(P[0], t1) > dis(P[0], t2);
}

void scanner() { //求凸包
    int i, j;
    find_pole_point();
    sort(P + 1, P + m, cmp);
    S[0] = P[0];
    S[1] = P[1];
    top = 1;
    for (i = 2; i < m; i++) {
        while (cross(S[top - 1], S[top], S[top], P[i]) < 0)
            top--;
        top++;
        S[top] = P[i];
    }
}

int main() {
    int i, j, ncase, l;
    while (true) {
        cin >> m >> l;
        if (cin.eof()) {
            break;
        }
        for (i = 0; i < m; i++) {
            cin >> P[i].x >> P[i].y;
        }
        scanner();
        double ans = 2 * 3.1415926 * l;
        for (i = 0; i <= top; i++) {
            ans += dis(S[i], S[(i + 1) % (top + 1)]);
        }
        // 使用cout输出时，要进行四舍五入处理
        cout << static_cast<int>(ans + 0.5) << endl; 
    }
    return 0;
}

题意总结

你需要帮建筑师围绕一个多边形形状的城堡建一圈围墙，满足：

围墙必须距离城堡至少 $L$ 英尺；

所用材料最少，即围墙的长度最短；

给出最小可能的围墙长度，结果是整数，四舍五入到 $1/12$ 英尺（也就是 $8$ 英寸）的精度。

解法思路

这是一个典型的几何凸包（Convex Hull）问题。

因为最短的外墙肯定是围绕在凸包外面；

所以：

先计算出原始点集的凸包；

然后求出凸包的周长；

最后加上圆角外扩的一圈：圆周长度为 $2\pi L$

因此，最小围墙长度为：

总长度=凸包周长+2𝜋𝐿（单位：英尺）

最后将结果四舍五入为整数输出即可。

代码实现：

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

const int MAXN = 1010;
const double PI = acos(-1.0);

struct Point {
    int x, y;
    bool operator < (const Point& rhs) const {
        return x < rhs.x || (x == rhs.x && y < rhs.y);
    }
};

Point points[MAXN], hull[MAXN];

int cross(const Point& o, const Point& a, const Point& b) {
    return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x); // 叉积
}

double distance(const Point& a, const Point& b) {
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}

// Andrew算法构建凸包
int convex_hull(Point* p, int n, Point* ch) {
    sort(p, p + n);
    int m = 0;
    
    // 下凸包
    for (int i = 0; i < n; ++i) {
        while (m >= 2 && cross(ch[m - 2], ch[m - 1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    }
    
    // 上凸包
    int k = m;
    for (int i = n - 2; i >= 0; --i) {
        while (m > k && cross(ch[m - 2], ch[m - 1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    }
    
    if (n > 1) m--; // 去掉最后一个重复点
    return m;
}

int main() {
    int N, L;
    cin >> N >> L;
    
    for (int i = 0; i < N; ++i) {
        cin >> points[i].x >> points[i].y;
    }
    
    int m = convex_hull(points, N, hull);
    
    double perimeter = 0;
    for (int i = 0; i < m; ++i) {
        perimeter += distance(hull[i], hull[(i + 1) % m]);
    }
    
    perimeter += 2 * PI * L; // 加上圆角部分的圆周长度，单位为英尺
    
    printf("%d\n", (int)(perimeter + 0.5)); // 四舍五入输出整数
    return 0;
}