1 条题解

  • 0
    @ 2025-7-17 10:07:46

    题意分析

    题目大意是:给定平面上的一些树(点),要用这些树作为围栏的顶点,围出一个尽可能大的牧场。牧场的面积决定了可以放多少头牛,每头牛至少需要50平方米的牧场面积。要求计算这个最大牧场能放多少头牛。

    解题思路

    1. 凸包(Convex Hull):首先需要找到这些点的凸包,因为凸包能够围出最大的面积。凸包是指包含所有点的最小凸多边形。
    2. 计算凸包面积:计算凸包所围成的多边形的面积。
    3. 计算牛的数量:将面积除以50,取整数部分即可得到牛的数量。

    代码实现

    代码使用了Andrew算法(或称为Graham扫描法)来求凸包,然后通过叉积计算凸包的面积。具体步骤如下:

    1. 输入处理:读取所有点的坐标,并找到最左下角的点作为凸包的起点。
    2. 极角排序:将其他点按照与起点的极角进行排序,如果极角相同,则按距离排序。
    3. 构建凸包:使用栈结构来维护凸包的点,确保每次新加入的点不会破坏凸包的凸性。
    4. 计算面积:利用叉积的性质计算凸包的面积。叉积的绝对值等于两个向量所夹平行四边形的面积,因此多边形的面积可以通过将多边形分割成多个三角形来计算。
    5. 输出结果:将面积除以50,取整数部分输出。

    标程

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    using namespace std;
    
    const int maxn = 10005;
    const double PI = acos(-1.0);
    
    struct Point {
        int x, y;
        Point() : x(0), y(0) {}
        Point(int x, int y) : x(x), y(y) {}
    } list[maxn];
    int stack[maxn], top;
    
    // 计算叉积 p0p1 × p0p2
    int cross(Point p0, Point p1, Point p2) {
        return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
    }
    
    // 计算 p1p2 的距离
    double dis(Point p1, Point p2) {
        return sqrt((double)(p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.y) * (p2.y - p1.y));
    }
    
    // 极角排序函数,角度相同则距离小的在前面
    bool cmp(Point p1, Point p2) {
        int tmp = cross(list[0], p1, p2);
        if (tmp > 0) return true;
        else if (tmp == 0 && dis(list[0], p1) < dis(list[0], p2)) return true;
        else return false;
    }
    
    // 输入,把最左下角放在 list[0],并且进行极角排序
    void init(int n) {
        Point p0;
        scanf("%d%d", &list[0].x, &list[0].y);
        p0.x = list[0].x;
        p0.y = list[0].y;
        int k = 0;
        for (int i = 1; i < n; ++i) {
            scanf("%d%d", &list[i].x, &list[i].y);
            if ((p0.y > list[i].y) || ((p0.y == list[i].y) && (p0.x > list[i].x))) {
                p0.x = list[i].x;
                p0.y = list[i].y;
                k = i;
            }
        }
        list[k] = list[0];
        list[0] = p0;
        sort(list + 1, list + n, cmp);
    }
    
    // graham扫描法求凸包,凸包顶点存在 stack 栈中
    void graham(int n) {
        if (n == 1) {
            top = 0;
            stack[0] = 0;
            return;
        }
        top = 1;
        stack[0] = 0;
        stack[1] = 1;
        for (int i = 2; i < n; ++i) {
            while (top > 0 && cross(list[stack[top - 1]], list[stack[top]], list[i]) <= 0) --top;
            stack[++top] = i;
        }
    }
    
    int main() {
        int n;
        while (~scanf("%d", &n)) {
            if (n < 3) { // 至少需要3个点才能围成多边形
                printf("0\n");
                continue;
            }
            init(n);
            graham(n);
            if (top < 2) { // 如果凸包的点数小于3,无法围成多边形
                printf("0\n");
                continue;
            }
            int area = 0;
            for (int i = 1; i < top; ++i) {
                area += cross(list[stack[0]], list[stack[i]], list[stack[i + 1]]);
            }
            area = abs(area) / 2;
            printf("%d\n", area / 50);
        }
        return 0;
    }
    

    代码解释

    1. 数据结构:使用Point结构体存储点的坐标。
    2. 叉积计算cross函数计算三个点的叉积,用于判断点的相对位置。
    3. 距离计算dis函数计算两点之间的距离。
    4. 极角排序cmp函数用于对点进行极角排序,确保凸包的正确构建。
    5. 凸包构建init函数初始化点集并排序,graham函数使用栈构建凸包。
    6. 面积计算:通过叉积的累加和计算凸包的面积,注意取绝对值并除以2得到实际面积。
    7. 输出结果:将面积除以50得到牛的数量并输出。

    该程序能够高效地处理最多10000个点,并正确计算出最大牧场的面积及可容纳的牛的数量。

    • 1

    信息

    ID
    2349
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    3
    已通过
    1
    上传者