得从大上个po开始说。
我不是根据矩形周长的AC代码了解了扫描线的思想么，然后我就开始根据矩形并周长的做法来yy矩形面积并的做法。事实上，我第一次yy出来的代码已经是正确的能够AC的了，然而因为http://wallacenews.tk/2016/05/01/囧/上所提到的原因，我没有AC。于是yy的代码被窝删掉了。然后我又照着AC的代码撸半天结果WA，好，最后发现是poj的锅。
^&%&&*&GUGUT756rygu日了狗了！
今天早上重新写了昨天自己yy的方法，提交，AC，日狗

贴yy的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define lson(x) (x << 1)
#define rson(x) (x << 1 | 1)
#define mid(l, r) ((l + r) >> 1)
#define MXN 207
using namespace std;
struct seg {
    double x1, x2;
    int atag;
    double y;
    int lx1, lx2;
    seg() {x1 = x2 = y = atag = 0;}
    seg(double a, double b, double c, int d):x1(a),x2(b),y(c),atag(d) {}
    bool operator<(const seg &b) const {
        return y == b.y ? atag > b.atag : y < b.y;
    }
} ss[MXN];
int cnt[MXN << 2 | 7];
int ll[MXN << 2 | 7], rr[MXN << 2 | 7];
double stree[MXN << 2 | 7];
double prefix[MXN], loc[MXN];
inline void pushup(int root, int l, int r) {
    if (cnt[root]) {
        stree[root] = loc[r] - loc[l - 1];
    } else if (l == r) {
        stree[root] = 0;
    } else {
        stree[root] = stree[lson(root)] + stree[rson(root)];
    }
}
void adddata(int root, int l, int r, int al, int ar, int data) {
    if (l > ar || r < al) return;
    if (l >= al && r <= ar) {
        cnt[root] += data;
        pushup(root, l, r);
        return;
    }
    adddata(lson(root), l, mid(l, r), al, ar, data);
    adddata(rson(root), mid(l, r) + 1, r, al, ar, data);
    pushup(root, l, r);
}
int main() {
    int n = 0;
    int t = 1;
    while (~scanf("%d", &n)) {
        if (n == 0) return 0;
        double a, b, c, d;
        int m = 0, cur = 0;
        for (int i = 0; i < n; ++i) {
            scanf("%lf %lf %lf %lf", &a, &b, &c, &d);
            ss[m++] = seg(a, c, b, 1);
            ss[m++] = seg(a, c, d, -1);
            loc[cur++] = a; loc[cur++] = c;
        }
        sort(loc, loc + cur);
        int sz = unique(loc, loc + cur) - loc;
        for (int i = 0; i < sz; ++i) {
            prefix[i + 1] = loc[i];
        }
        for (int i = 0; i < m; ++i) {
            ss[i].lx1 = lower_bound(loc, loc + sz, ss[i].x1) - loc + 1;
            ss[i].lx2 = lower_bound(loc, loc + sz, ss[i].x2) - loc + 1;
        }
        sort(ss, ss + m);
        double last = 0, resu = 0;
        for (int i = 0; i < m; ++i) {
            adddata(1, 1, sz, ss[i].lx1, ss[i].lx2 - 1, ss[i].atag);
            if (i != m - 1) resu += fabs(stree[1]) * (ss[i + 1].y - ss[i].y);
            last = stree[1];
        }
        printf("Test case #%d\nTotal explored area: %.2lf\n\n", t++, resu);
    }
}

这里处理线段的方法是将离散后的右端减去1，这样一个节点[l, r]所表示的区间就是[rev(l), rev(r + 1)]，
也就是说叶子节点i表示的是一个单位线段从[rev(i), rev(i + 1)]。

贴上照着别人的代码撸出来的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define lson(x) (x << 1)
#define rson(x) (x << 1 | 1)
#define mid(l, r) ((l + r) >> 1)
#define MXN 207
using namespace std;
struct seg {
    double x1, x2;
    int atag;
    double y;
    int lx1, lx2;
    seg() {x1 = x2 = y = atag = 0;}
    seg(double a, double b, double c, int d):x1(a),x2(b),y(c),atag(d) {}
    bool operator<(const seg &b) const {
        return y == b.y ? atag > b.atag : y < b.y;
    }
} ss[MXN];
int cnt[MXN << 2 | 7];
int ll[MXN << 2 | 7], rr[MXN << 2 | 7];
double stree[MXN << 2 | 7];
double prefix[MXN], loc[MXN];
void build(int root, int l, int r) {
    stree[root] = cnt[root] = 0;
    ll[root] = l;
    rr[root] = r;
    if (l + 1 == r) return;
    build(lson(root), l, mid(l, r));
    build(rson(root), mid(l, r), r);
}
inline void pushup(int root) {
    if (cnt[root]) {
        stree[root] = prefix[rr[root]] - prefix[ll[root]];
    } else if (ll[root] + 1 == rr[root]) {
        stree[root] = 0;
    } else {
        stree[root] = stree[lson(root)] + stree[rson(root)];
    }
}
void adddata(int root, int l, int r, int data) {
    if (ll[root] == l && rr[root] == r) {
        cnt[root] += data;
    } else if (r <= mid(ll[root], rr[root])) {
        adddata(lson(root), l, r, data);
    } else if (l >= mid(ll[root], rr[root])) {
        adddata(rson(root), l, r, data);
    } else {
        adddata(lson(root), l, mid(ll[root], rr[root]), data);
        adddata(rson(root), mid(ll[root], rr[root]), r, data);
    }
    pushup(root);
}

int main() {
    int n = 0;
    int t = 1;
    while (~scanf("%d", &n)) {
        if (n == 0) return 0;
        double a, b, c, d;
        int m = 0, cur = 0;
        for (int i = 0; i < n; ++i) {
            scanf("%lf %lf %lf %lf", &a, &b, &c, &d);
            ss[m++] = seg(a, c, b, 1);
            ss[m++] = seg(a, c, d, -1);
            loc[cur++] = a; loc[cur++] = c;
        }
        sort(loc, loc + cur);
        int sz = unique(loc, loc + cur) - loc;
        for (int i = 0; i < sz; ++i) {
            prefix[i + 1] = loc[i];
        }
        for (int i = 0; i < m; ++i) {
            ss[i].lx1 = lower_bound(loc, loc + sz, ss[i].x1) - loc + 1;
            ss[i].lx2 = lower_bound(loc, loc + sz, ss[i].x2) - loc + 1;
        }
        build(1, 1, sz);
        sort(ss, ss + m);
        for (int i = 0; i <= sz; ++i) {
        }
        double last = 0, resu = 0;
        for (int i = 0; i < m; ++i) {
            adddata(1, ss[i].lx1, ss[i].lx2, ss[i].atag);
            if (i != m - 1) resu += fabs(stree[1]) * (ss[i + 1].y - ss[i].y);
            last = stree[1];
        }
        printf("Test case #%d\nTotal explored area: %.2lf\n\n", t++, resu);
    }
}

这里表示线段的方法是[l, r]表示[rev(l), rev(r)]，需要注意的是判断叶子节点的方法从l == r变成了l + 1 == r，判断是否包含区间的方式也发生了变化，为l == ll[root] && r = rr[root]，除此之外每个节点的左右界最好在最开始的时候通过build的方式算出来。