覆盖的面积

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3534    Accepted Submission(s): 1731

给定平面上若干矩形,求出被这些矩形覆盖过至少两次的区域的面积.

       思路：

       线段树 + 扫描线 + 离散化。len 维护该区间内已被覆盖的长度，one 维护这个区间内覆盖一次的长度，two 维护这个区间内被覆盖两次或者两次以上的长度。每个区间覆盖的长度 len 要始终等于 one + two。主要是 push_up 的不同：

void push_up (int node, int l, int r) {
        if (cover[node] >= 2) {
                len[node] = two[node] = yy[r] - yy[l];
                one[node] = 0;
        //当覆盖两次，则 one 应该为0
        } else if (cover[node] == 1) {
                len[node] = yy[r] - yy[l];
                two[node] = two[node << 1] + two[node << 1 | 1];
                two[node] += (one[node << 1] + one[node << 1 | 1]);
                one[node] = len[node] - two[node];
        //当覆盖一次，two 应该为左右儿子 two 之和，加上它这层在原来左右儿子 one 上的和
        //总长减去 two 的长度就是 one 的长度，
        } else if (r - l == 1) {
                len[node] = two[node] = one[node] = 0;
        //未被覆盖且是叶子节点则为 0
        } else {
                len[node] = len[node << 1] + len[node << 1 | 1];
                two[node] = two[node << 1] + two[node << 1 | 1];
                one[node] = one[node << 1] + one[node << 1 | 1];
        //未被覆盖且不是叶子节点则全为左右儿子各部分之和
        }
}

       AC：

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAX = 2050 * 2 * 3;

typedef struct {
        double x, y1, y2;
        int temp;
}node;

node line[2050];
double yy[2050 * 2];
double one[MAX], two[MAX], len[MAX];
int cover[MAX];

bool cmp (node a, node b) {
        if (a.x != b.x) return a.x < b.x;
        return a.temp > b.temp;
}

void push_up (int node, int l, int r) {
        if (cover[node] >= 2) {
                len[node] = two[node] = yy[r] - yy[l];
                one[node] = 0;
        } else if (cover[node] == 1) {
                len[node] = yy[r] - yy[l];
                two[node] = two[node << 1] + two[node << 1 | 1];
                two[node] += (one[node << 1] + one[node << 1 | 1]);
                one[node] = len[node] - two[node];
        } else if (r - l == 1) {
                len[node] = two[node] = one[node] = 0;
        } else {
                len[node] = len[node << 1] + len[node << 1 | 1];
                two[node] = two[node << 1] + two[node << 1 | 1];
                one[node] = one[node << 1] + one[node << 1 | 1];
        }
}

void build (int node, int l, int r) {
        if (r - l == 1) {
                cover[node] = len[node] = 0;
                two[node] = one[node] = 0;
        } else {
                int mid = (r + l) >> 1;
                build(node << 1, l, mid);
                build(node << 1 | 1, mid, r);
                push_up(node, l, r);
        }
}

void updata (int node, int l, int r, int cl, int cr, int c) {
        if (cl > r || cr < l) return;
        if (cl <= l && cr >= r) {
                cover[node] += c;
                push_up(node, l, r);
                return;
        }
        if(r - l == 1) return;

        int mid = (r + l) >> 1;
        if (l <= mid) updata(node << 1, l, mid, cl, cr, c);
        if (r >= mid) updata(node << 1 | 1, mid, r, cl, cr, c);
        push_up(node, l, r);
}

int main() {
        int t;
        scanf("%d", &t);

        while (t--) {
                int n;
                scanf("%d", &n);

                int ans = 0, m = 0;
                while (n--) {
                        double x1, y1, x2, y2;
                        scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);

                        line[ans].x = x1;
                        line[ans].y1 = y1;
                        line[ans].y2 = y2;
                        line[ans++].temp = 1;

                        line[ans].x = x2;
                        line[ans].y1 = y1;
                        line[ans].y2 = y2;
                        line[ans++].temp = -1;

                        yy[m++] = y1;
                        yy[m++] = y2;
                }

                sort(yy, yy + m);
                m = unique(yy, yy + m) - yy;

                sort(line, line + ans, cmp);
                build(1, 0, m - 1);

                double res = 0;
                for (int i = 0; i < ans; ++i) {
                        int ll = lower_bound(yy, yy + m, line[i].y1) - yy;
                        int rr = lower_bound(yy, yy + m, line[i].y2) - yy;

                        if(i) res += two[1] * (line[i].x - line[i - 1].x);
                        
                        updata(1, 0, m - 1, ll, rr, line[i].temp);
                }

                printf("%.2lf\n", res);

        }

        return 0;
}