题目链接：codevs3044-矩形面积并

题意：

二维坐标，给n个矩阵，求面积。

题解：

线段树+扫描线。

扫描线的方向可以任定，我选的方向是从下到上，所以对于每个矩形，只需要考虑它的上下两边，即(L,R,U,F)，LR表示边的顶点的横坐标，U表示纵坐标，F为标记，表示该边是矩形的顶边还是底边。

然后从较小的纵坐标开始枚举边，若当前边为底边，则在线段树上对这个区域进行标记，若遇到顶边，则取消标记。每扫描到一条边时，通过线段树快速计算此时覆盖在x轴上的总长度为L，并计算与下一条边的距离为S，当前的答案为ans+=L*S。

参考代码：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 209;
int n;
struct node
{
    double x1, x2, y;
    int f;
} a[MAXN << 2];
double has[MAXN << 2], sum[MAXN << 2];
int lazy[MAXN << 2];
bool cmp(node x, node y)
{
    return x.y < y.y;
}
int getid(double x)
{
    int l = 1, r = 2 * n + 1;
    while (l < r)
    {
        int mid = (l + r) / 2;
        if (has[mid] < x)
            l = mid + 1;
        else if (has[mid] == x)
            return mid;
        else
            r = mid;
    }
}
void pushup(int l, int r, int rt)
{
    if (lazy[rt])
        sum[rt] = has[r + 1] - has[l];
    else if (l == r)
        sum[rt] = 0;
    else
        sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}

void update(int L, int R, int val, int l, int r, int rt)
{
    if (L <= l && r <= R)
    {
        lazy[rt] += val;
        pushup(l, r, rt);
        return;
    }
    int mid = (l + r) / 2;
    if (L <= mid)
        update(L, R, val, l, mid, rt << 1);
    if (R > mid)
        update(L, R, val, mid + 1, r, rt << 1 | 1);
    pushup(l, r, rt);
}
int main()
{
    while (scanf("%d", &n) && n)
    {
        memset(sum, 0, sizeof(sum));
        memset(lazy, 0, sizeof(lazy));
        for (int i = 1; i <= n; i++)
        {
            double x1, y1, x2, y2;
            scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
            a[i * 2 - 1].x1 = a[i * 2].x1 = x1;
            a[i * 2 - 1].x2 = a[i * 2].x2 = x2;
            a[i * 2 - 1].y = y1, a[i * 2 - 1].f = 1;
            a[i * 2].y = y2, a[i * 2].f = -1;
            has[i * 2 - 1] = x1, has[i * 2] = x2;
        }
        sort(has + 1, has + n * 2 + 1);
        sort(a + 1, a + n * 2 + 1, cmp);
        double ans = 0;
        for (int i = 1; i <= n * 2; i++)
        {
            int l = getid(a[i].x1), r = getid(a[i].x2) - 1;
            if (l <= r)
                update(l, r, a[i].f, 1, 2 * n, 1);
            ans += sum[1] * (a[i + 1].y - a[i].y);
        }
        printf("%.2f\n", ans);
    }
    return 0;
}