算法原理：线段树

基础习题: http://poj.org/problem?id=1177

#include <iostream>
#include <stdio.h>
#include <algorithm>
#define lson (x << 1)
#define rson (x << 1 | 1)
using namespace std;
const int MAXN = 2e4;
int n, X[MAXN << 1];
int x1, y1, x2, y2, pre = 0; /* 先初始化为 0 */

struct ScanLine {
    int l, r, h, mark;
    if(h == rhs.h)
        return mark > rhs.mark;
    return h < rhs.h;
//      注意！这里是后来被 hack 掉以后加上去的
//      在此感谢 @leprechaun_kdl 指出问题
//      如果出现了两条高度相同的扫描线，也就是两矩形相邻
//      那么需要先扫底边再扫顶边，否则就会多算这条边
//      这个对面积并无影响但对周长并有影响
//      hack 数据：2 0 0 4 4 0 4 4 8 输出应为：24
} line[MAXN];

struct SegTree {
    int l, r, sum, len, c;
//  c表示区间线段条数
    bool lc, rc;
//  lc, rc分别表示左、右端点是否被覆盖
//  统计线段条数(tree[x].c)会用到
} tree[MAXN << 2];

void build_tree(int x, int l, int r) {
    tree[x].l = l, tree[x].r = r;
    tree[x].lc = tree[x].rc = false;
    tree[x].sum = tree[x].len = 0;
    tree[x].c = 0;
    if(l == r)
        return;
    int mid = (l + r) >> 1;
    build_tree(lson, l, mid);
    build_tree(rson, mid + 1, r);
}

void pushup(int x) {
    int l = tree[x].l, r = tree[x].r;
    if(tree[x].sum) {
        tree[x].len = X[r + 1] - X[l];
        tree[x].lc = tree[x].rc = true;
        tree[x].c = 1;
//      做好相应的标记
    }
    else {
        tree[x].len = tree[lson].len + tree[rson].len;
        tree[x].lc = tree[lson].lc, tree[x].rc = tree[rson].rc;
        tree[x].c = tree[lson].c + tree[rson].c;
//      如果左儿子左端点被覆盖，那么自己的左端点也肯定被覆盖；右儿子同理
        if(tree[lson].rc && tree[rson].lc)
            tree[x].c -= 1;
//      如果做儿子右端点和右儿子左端点都被覆盖，
//      那么中间就是连续的一段，所以要 -= 1
    }
}

void edit_tree(int x, int L, int R, int c) {
    int l = tree[x].l, r = tree[x].r;
    if(X[l] >= R || X[r + 1] <= L)
        return;
    if(L <= X[l] && X[r + 1] <= R) {
        tree[x].sum += c;
        pushup(x);
        return;
    }
    edit_tree(lson, L, R, c);
    edit_tree(rson, L, R, c);
    pushup(x);
}

ScanLine make_line(int l, int r, int h, int mark) {
    ScanLine res;
    res.l = l, res.r = r,
    res.h = h, res.mark = mark;
    return res;
}
//  POJ 不这样做就会CE，很难受

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        line[i * 2 - 1] = make_line(x1, x2, y1, 1);
        line[i * 2] = make_line(x1, x2, y2, -1);
        X[i * 2 - 1] = x1, X[i * 2] = x2;
    }
    n <<= 1;
    sort(line + 1, line + n + 1);
    sort(X + 1, X + n + 1);
    int tot = unique(X + 1, X + n + 1) - X - 1;
    build_tree(1, 1, tot - 1);
    int res = 0;
    for(int i = 1; i < n; i++) {
        edit_tree(1, line[i].l, line[i].r, line[i].mark);
        res += abs(pre - tree[1].len);
        pre = tree[1].len;
//      统计横边
        res += 2 * tree[1].c * (line[i + 1].h - line[i].h);
//      统计纵边
    }
    res += line[n].r - line[n].l;
//  特判一下枚举不到的最后一条扫描线
    printf("%d", res);
    return 0;
}