学步园

题意：求n个矩形面积的并（1 <= n <= 1000，坐标范围：0 <= x1 < x2 <= 50000;0 <= y1 < y2 <= 50000）。

题目链接：http://poj.org/problem?id=1389

——>>思路与poj1151是一样的，只是输入输出变了一些。。。提取出所有矩形的所有纵向边作为扫描线，从左往右扫描，每处理一条扫描线时，下一条扫描线与当前扫描线的距离乘上当前已覆盖纵向边的长度是一个部分面积，将这些面积累加起来就是n个矩形面积的并。。

而当前覆盖到纵向边长度可通过线段树来维护。。空间上则要求先对所有点的纵坐标进行离散化。。

总时间复杂度为O(nlogn)。。

#include <cstdio>
#include <algorithm>

using namespace std;

#define lc (o<<1)
#define rc ((o<<1)+1)

const int MAXN = 1000 + 10;

int y[MAXN<<1];
int cnt;

struct Scanline {
    int x;
    int y1, y2;
    bool is_left;

    bool operator < (const Scanline& e) const {
        return x < e.x;
    }
} scanlines[MAXN<<1];

struct Node {
    int L, R;
    int len;
    int cover;
} nodes[MAXN<<3];

int point_to(int x) {
    return lower_bound(y, y + cnt, x) - y;
}

void build(int o, int L, int R) {
    nodes[o].L = L;
    nodes[o].R = R;
    nodes[o].len = 0;
    nodes[o].cover = 0;
    if(L + 1 == R) return;
    int M = (L + R) >> 1;
    build(lc, L, M);
    build(rc, M, R);
}

void maintain_len(int o) {
    if(nodes[o].cover > 0) {
        nodes[o].len = y[nodes[o].R] - y[nodes[o].L];
    }
    else if(nodes[o].L + 1 == nodes[o].R) {
        nodes[o].len = 0;
    }
    else {
        nodes[o].len = nodes[lc].len + nodes[rc].len;
    }
}

void my_insert(int o, int ql, int qr) {
    if(ql <= nodes[o].L && nodes[o].R <= qr) {
        nodes[o].cover++;
        maintain_len(o);
        return;
    }
    int M = (nodes[o].L + nodes[o].R) >> 1;
    if(ql < M) my_insert(lc, ql, qr);
    if(qr > M) my_insert(rc, ql, qr);
    maintain_len(o);
}

void my_delete(int o, int ql, int qr) {
    if(ql <= nodes[o].L && nodes[o].R <= qr) {
        nodes[o].cover--;
        maintain_len(o);
        return;
    }
    int M = (nodes[o].L + nodes[o].R) >> 1;
    if(ql < M) my_delete(lc, ql, qr);
    if(qr > M) my_delete(rc, ql, qr);
    maintain_len(o);
}

int main()
{
    int n = 0;
    int x1, y1, x2, y2;
    while(scanf("%d%d%d%d", &x1, &y1, &x2, &y2) == 4) {
        if(x1 == -1 && y1 == -1 && x2 == -1 && y2 == -1) {
            if(n == 0) continue;
        }
        else {
            scanlines[n<<1].x = x1;
            scanlines[n<<1].y1 = y1;
            scanlines[n<<1].y2 = y2;
            scanlines[n<<1].is_left = true;
            scanlines[(n<<1)+1].x = x2;
            scanlines[(n<<1)+1].y1 = y1;
            scanlines[(n<<1)+1].y2 = y2;
            scanlines[(n<<1)+1].is_left = false;
            y[n<<1] = y1;
            y[(n<<1)+1] = y2;
            n++;
            continue;
        }

        sort(y, y + 2*n);
        cnt = unique(y, y + 2*n) - y;

        sort(scanlines, scanlines + 2*n);
        build(1, 0, cnt-1);
        int area = 0;
        for(int i = 0; i < 2*n-1; i++) {
            if(scanlines[i].is_left) {
                my_insert(1, point_to(scanlines[i].y1), point_to(scanlines[i].y2));
            }
            else {
                my_delete(1, point_to(scanlines[i].y1), point_to(scanlines[i].y2));
            }
            area += (scanlines[i+1].x - scanlines[i].x) * nodes[1].len;
        }
        printf("%d\n", area);
        n = 0;
    }
    return 0;
}