POJ

分析

扫描线板子？

线段树维护一下总覆盖长度就行了。

然而这东西不是很好维护，细节见代码。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

const int MAXN=(100<<1)+10;

double S[MAXN];
struct node {
    double x,y1,y2; int w;
    bool operator <(const node& rhs) const {
        return (x<rhs.x)||(x==rhs.x&&w<rhs.w);
    }
} p[MAXN];

struct Segment_Tree {
    int cntv[MAXN<<2]; double lenv[MAXN<<2];
#define lson (o<<1)
#define rson (o<<1|1)
#define mid ((l+r)>>1)
    inline void pushup(int o,int l,int r) {
        if (cntv[o]) lenv[o]=S[r+1]-S[l];
        else if (l==r) lenv[o]=0;
        else lenv[o]=lenv[lson]+lenv[rson];
    }
    inline void init() {
        memset(cntv,0,sizeof(cntv));
        memset(lenv,0,sizeof(lenv));
    }
    inline void update(int o,int l,int r,int ql,int qr,int w) {
        if (ql<=l&&r<=qr) { cntv[o]+=w; pushup(o,l,r); return; }
        if (ql<=mid) update(lson,l,mid,ql,qr,w);
        if (qr>mid) update(rson,mid+1,r,ql,qr,w);
        pushup(o,l,r);
    }
#undef lson
#undef rson
#undef mid
} T;

int main() {
    int n,Test=0;
    while (scanf("%d",&n)==1) {
        if (!n) break;
        T.init(); ++Test;
        int top=0,tot=0;
        for (re int i=1;i<=n;++i) {
            double lx,ly,rx,ry;
            scanf("%lf%lf%lf%lf",&lx,&ly,&rx,&ry);
            p[++tot]=(node){lx,ly,ry,1};
            p[++tot]=(node){rx,ly,ry,-1};
            S[++top]=ly,S[++top]=ry;
        }
        sort(S+1,S+top+1); sort(p+1,p+tot+1);
        top=unique(S+1,S+top+1)-S-1;
        double ans=0.0;
        for (re int i=1;i<tot;++i) {
            int L=lower_bound(S+1,S+top+1,p[i].y1)-S;
            int R=lower_bound(S+1,S+top+1,p[i].y2)-S-1;
            if (L<=R) T.update(1,1,top,L,R,p[i].w);
            ans+=(p[i+1].x-p[i].x)*T.lenv[1];
        }
        printf("Test case #%d\nTotal explored area: %.2f\n\n",Test,ans);
    }
    return 0;
}