本文共 1839 字，大约阅读时间需要 6 分钟。
该题就是给定N个矩形，求出叠加之后的面积，与求面积交类似，就是覆盖次数没有了要求。
代码如下：
#include #include #include #include #include #include #define MAXN 205 using namespace std; struct Node { double x, y1, y2; int lr; bool operator < (Node t) const { return t.x-x>1e-6; } }e[MAXN*2]; struct { int l, r; int cover; }seg[MAXN*3]; double yy[MAXN*2]; void creat(int f, int l, int r) { int mid = (l+r)>>1; seg[f].l = l, seg[f].r = r; seg[f].cover = 0; if (r - l > 1) { creat(f<<1, l, mid); creat(f<<1|1, mid, r); } } void modify(int f, int l, int r, int val) { int mid = (seg[f].l + seg[f].r) >> 1; if (seg[f].l == l && seg[f].r == r) { seg[f].cover += val; } else if (seg[f].r - seg[f].l > 1) { if (r <= mid) modify(f<<1, l, r, val); else if (l >= mid) modify(f<<1|1, l, r, val); else { modify(f<<1, l, mid, val); modify(f<<1|1, mid, r, val); } } } void query(int f, double &ans) { if (seg[f].cover > 0) { ans += yy[seg[f].r] - yy[seg[f].l]; } else if (seg[f].r - seg[f].l > 1) { query(f<<1, ans); query(f<<1|1, ans); } } int main() { double x1, y1, x2, y2, ans, res; int N, ca = 1;; while (scanf("%d", &N), N) { res = 0; map mp; for (int i = 1, j = 1; i <= N; ++i, j += 2) { scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2); e[j].x = x1, e[j].y1 = y1, e[j].y2 = y2; e[j].lr = 1; e[j+1].x = x2, e[j+1].y1 = y1, e[j+1].y2 = y2; e[j+1].lr = -1; yy[j] = y1, yy[j+1] = y2; } sort(e+1, e+1+2*N); sort(yy+1, yy+1+2*N); int cnt = unique(yy+1, yy+1+2*N) - (yy+1); creat(1, 1, cnt); for (int i = 1; i <= cnt; ++i) { mp[yy[i]] = i; // printf("yy= %lf\n", yy[i]); } for (int i = 1; i < 2*N; ++i) { ans = 0; modify(1, mp[e[i].y1], mp[e[i].y2], e[i].lr); query(1, ans); res += ans * (e[i+1].x - e[i].x); // printf("res = %lf\n", res); } printf("Test case #%d\nTotal explored area: %.2lf\n\n", ca++, res); } return 0; }
转载地址：http://dztpo.baihongyu.com/