1 条题解

  • 0
    @ 2025-5-6 20:22:40

    问题分析

    1. 每个王国是平面上的凸包
    2. 导弹击中凸包内部则摧毁发电厂
    3. 需要计算被摧毁王国的总面积

    关键点

    • 凸包计算
    • 点是否在多边形内的判断
    • 面积累加

    解题步骤

    1. 对每个王国计算凸包
    2. 检查每个导弹是否在凸包内
    3. 标记被击中的王国
    4. 计算被标记王国的总面积
    #include <cstring>
    #include <algorithm>
    using namespace std;
    int const MAX = 105;
    int n;
    struct POINT {
        int x, y;
    }base, p[MAX];
     
    struct AREA {
        int top;
        double area;
        POINT stk[MAX];
    }a[25];
    bool vis[25];
     
    void getBase() {  
        scanf("%d %d", &p[0].x, &p[0].y);  
        base.x = p[0].x;  
        base.y = p[0].y;  
        int pos = 0;  
        for (int i = 1; i < n; i ++) {  
            scanf("%d %d", &p[i].x, &p[i].y);  
            if (p[i].y < base.y || (p[i].y == base.y && p[i].x < base.x)) {  
                base.x = p[i].x;  
                base.y = p[i].y;  
                pos = i;  
            }  
        }  
        swap(p[0], p[pos]);  
    }  
     
    int getDist(POINT p1, POINT p2) {
        return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
    }
     
    int getCross(POINT p0, POINT p1, POINT p2) {
        return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
    }
     
    bool cmp(POINT p1, POINT p2) {
        if (getCross(base, p1, p2) == 0) {
            return getDist(base, p1) < getDist(base, p2);
        }
        if (getCross(base, p1, p2) > 0) {
            return true;
        }
        return false;
    }
     
    void getConvex(int i) {
        sort(p + 1, p + n, cmp);
        a[i].stk[0] = p[0];
        a[i].stk[1] = p[1];
        a[i].top = 1;
        for (int j = 2; j < n; j ++) {
            while (a[i].top > 0 && getCross(a[i].stk[a[i].top - 1], a[i].stk[a[i].top], p[j]) <= 0) {
                a[i].top --;
            }
            a[i].stk[++ a[i].top] = p[j];
        }
    }
     
    void getArea(int i) {
        a[i].stk[++ a[i].top] = p[0];
        for (int j = 0; j < a[i].top; j ++) {
            a[i].area += getCross(base, a[i].stk[j], a[i].stk[j + 1]);
        }
        a[i].area /= 2.0;
    }
     
    int main() {
        int cnt = 0;
        while(scanf("%d", &n) && n != -1) {
            getBase();
            getConvex(cnt);
            getArea(cnt);
            cnt ++;
        }
        POINT t;
        double ans = 0;
        while(scanf("%d %d", &t.x, &t.y) != EOF) {
            bool flag = false;
            for (int i = 0; i < cnt && !flag; i ++) {
                if (!vis[i]) {
                    for (int j = 0; j < a[i].top && !flag; j ++) {
                        if (getCross(a[i].stk[0], a[i].stk[j], t) >= 0 &&  getCross(a[i].stk[0], a[i].stk[j + 1], t) <= 0) {
                            if (getCross(a[i].stk[j], t, a[i].stk[j + 1]) <= 0) {
                                vis[i] = true;
                                flag = true;
                                ans += a[i].area;
                            }
                        }
                    } 
                }
            }
        } 
        printf("%.2f\n", ans);
    }
    
    • 1

    信息

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