HDU 1255 覆盖的面积[离散化 + 扫描线 + 线段树]

http://acm.hdu.edu.cn/showproblem.php?pid=1255
给定平面上若干矩形,求出被这些矩形覆盖过至少两次的区域的面积.

这里写图片描述

这题比hdu1542复杂一点点(here)，就是要求至少被覆盖两次。
其实也没复杂多少。在线段树维护的时候只需用 len[node][i] 表示 node 结点被覆盖至少 i 次的长度就好了。

精度问题？我样例跑出来是7.62，但也A了。。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;

#define rep(i,f,t) for(int i = (f),_end = (t); i <= _end; ++i)
#define clr(c,x) memset(c,x,sizeof(c));
#define debug(x) cout<<"debug  "<<x<<endl;

const double eps = 1e-9;

typedef pair<double,double> Pr;
vector<double> vs;
int n;

struct Node{
    double x,y1,y2;
    int from,to;
    bool flag;
    Node(double xx,double yy1,double yy2,double f)
        :x(xx),y1(yy1),y2(yy2),flag(f){}
    bool operator<(const Node &n2)const{
        return x < n2.x;
    }
};
vector<Node> line;

bool equ(double a,double b){ return fabs(a-b)<eps; }
bool cmp(double a,double b){
    if(equ(a,b))return false;
    return a < b;
}

const int maxn = 2002<<2;
#define MID int mid = (L+R)>>1;
#define CHD int lc = node<<1, rc = node<<1|1;

struct sgt{
    int cov[maxn];
    double len[maxn][3];
    void init(){
        clr(cov,0);
        clr(len,0);
    }
    void update(int from,int to,int tp,int node,int L,int R){
        if(from <= L && R <= to){
            cov[node] += tp;
        }else{
            MID;CHD;
            if(from <= mid)update(from,to,tp,lc,L,mid);
            if(to > mid)update(from,to,tp,rc,mid+1,R);
        }
        maintain(node,L,R);
    }
    void maintain(int node,int L,int R){
        double tot = vs[R]-vs[L-1];
        clr(len[node],0);
        rep(i,1,min(2,cov[node]))
            len[node][i] = tot;
        if(L==R)return;
        CHD;
        rep(i,cov[node]+1,2){
            len[node][i] = len[lc][i-cov[node]] + len[rc][i-cov[node]];
        }
    }
    double query(){
        return len[1][2];
    }
}tree;

void pre(){
    sort(vs.begin(),vs.end());
    vs.erase(unique(vs.begin(),vs.end(),equ),vs.end());
    rep(i,0,line.size()-1){
        line[i].from = lower_bound(vs.begin(),vs.end(),line[i].y1,cmp) - vs.begin();
        line[i].to = lower_bound(vs.begin(),vs.end(),line[i].y2,cmp) - vs.begin();
    }
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        vs.clear();
        line.clear();
        scanf("%d",&n);
        rep(i,1,n){
            double x1,y1,x2,y2;
            scanf("%lf%lf%lf%lf", &x1,&y1,&x2,&y2);
            vs.push_back(y1);
            vs.push_back(y2);
            line.push_back(Node(x1,y1,y2,true));
            line.push_back(Node(x2,y1,y2,false));
        }
        pre();//离散化
        sort(line.begin(),line.end());
        double ans = 0;
        double x = 0;
        rep(i,0,line.size()-1){
            int v = (line[i].flag ? 1 : -1);
            double len = tree.query();
            ans += (line[i].x-x)*len;
            x = line[i].x;
            tree.update(line[i].from+1,line[i].to,v,1,1,vs.size()-1);
        }
        printf("%.2lf
",ans);
    }
    return 0;
}