(话说这篇题解我在洛谷发过,所以图有水印...)

思路

扫描线经典题.

图1
我们从左到右扫描所有的纵向边.

图2 - 红色边即为依次扫描到的边.

这些边可以用一个结构体记录.需要记录横坐标,上下边界(纵坐标),是一个矩形的结束还是开始.
扫描这些边时,我们用数据结构维护每个位置纵坐标被矩形覆盖了多少.
如样例,当至时,覆盖了至的部分,当至时,覆盖了至的部分,以此类推.注意覆盖的部分不一定是连续的,因此我们数据结构只维护覆盖的长度,即覆盖了至,我们只记录覆盖长度为.
然后我们就可以每一段分别求出覆盖的面积并加起来就是答案了.

图3 - 这些面积加起来就是答案

然后我们还需要解决怎么维护覆盖长度.
如果暴力的话复杂度就是,很明显不够优秀.
我们可以使用线段树来维护.具体来说.就是线段树每个节点记录该节点所在区间覆盖的次数(该节点子节点就不用加上去了),是一个矩形的开始,覆盖次数,是一个矩形的结束,覆盖次数.
如果某一个节点覆盖次数为,该节点的权值(即该节点所代表区间总共覆盖的长度)就是该节点左右儿子权值和,否则该节点的权值即为该节点所在区间总长.
因为矩形左右两边都是相等的,所以这样做是正确的.
还有,需要注意一点,线段树维护的是每一小段区间覆盖次数,而不是点的覆盖次数,记录点的覆盖次数没有意义.
具体请参考代码.

代码

牛客网最后多输出一个换行会WA...

#include<bits/stdc++.h>
using namespace std;
#define MAXN 105

int T, N, NN, n;
double a[MAXN << 1], b[MAXN << 1], ans;
struct node{
    int u, d, v; double x;
    bool operator < ( const node &t )const{ return x < t.x; }
}q[MAXN << 1];

double tr[MAXN << 3]; int s[MAXN << 3];

void Add( int c, int l, int r, int L, int R, int v ){
    if ( L > r || l > R ) return;
    const int mid((l + r) >> 1), ls(c << 1), rs(ls | 1);
    if ( L <= l && r <= R ) return tr[c] = !(s[c] += v) ? l == r ? 0 : tr[ls] + tr[rs] : ( b[r + 1] - b[l] ), void();
    Add( ls, l, mid, L, R, v ), Add( rs, mid + 1, r, L, R, v );
    !s[c] ? tr[c] = tr[ls] + tr[rs] : 0;
}

int main(){
    while ( ~scanf( "%d", &N ) && N ){
        NN = N << 1;
        for ( int i = 0; i < NN; i += 2 )
            scanf( "%lf%lf%lf%lf", &q[i].x, a + i, &q[i + 1].x, a + i + 1 ),
            b[i] = a[i], b[i + 1] = a[i + 1], q[i].v = 1, q[i + 1].v = -1;
        sort( b, b + NN ), n = unique( b, b + NN ) - b;
        for ( int i = 0, t1, t2; i < NN; i += 2 )
            t1 = lower_bound( b, b + n, a[i] ) - b, q[i].d = q[i + 1].d = t1,
            t2 = lower_bound( b, b + n, a[i+1] ) - b, q[i].u = q[i + 1].u = t2;
        sort( q, q + NN ), Add( 1, 0, n - 2, q[0].d, q[0].u - 1, q[0].v );
        ans = 0;
        for ( int i = 1; i < NN; ++i )
            ans += tr[1] * ( q[i].x - q[i - 1].x ),
            Add( 1, 0, n - 2, q[i].d, q[i].u - 1, q[i].v );
        if ( T ) printf("\n");
        printf( "Test case #%d\nTotal explored area: %.2lf\n", ++T, ans );
    }
    return 0;
}