1 条题解
-
0
问题分析:
- 每个王国是平面上的凸包
- 导弹击中凸包内部则摧毁发电厂
- 需要计算被摧毁王国的总面积
关键点:
- 凸包计算
- 点是否在多边形内的判断
- 面积累加
解题步骤:
- 对每个王国计算凸包
- 检查每个导弹是否在凸包内
- 标记被击中的王国
- 计算被标记王国的总面积
#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
- 上传者