给定平面上若干矩形,求出被这些矩形覆盖的区域的面积。

对所有矩形的 y 坐标进行离散化，然后对所有竖线段按 x 坐标排序。标记矩形左边的线段是“入边”，右边的是“出边”。从左往右扫描。对于线段 li，只要知道当前所有竖线段的长度并 H，则 li−1 到 li 区间的面积就是 H×(xi−xi−1) ，将其加到答案中。

要高效的维护区间信息，首先想到的是线段树。然后，如果该边是“入边”，则将此边加到线段树中，否则，线段树中一定维护着这条边对应的“入边”，将它删除掉。

对于每一条“入边”，在遇到它所对应的“出边”之前，它都会影响着右边的面积，所有这些“入边”的并就是它们共同产生的影响。只要在下一条边加入之前统计出当前这部分的面积，那扫描完所有边后被这些矩形覆盖的面积就计算出来了。

还有一个问题。普通的线段树都是顶点式的，而这里要的是坐标区间式的。这有两种方法解决，一种是改变结点的闭合方式，如左闭右开，结点[l,r) 表示线段 [l,r] 。我是改变结点的表示含义，结点i 表示第 i 段线段，如结点[1,1] 表示 [0,1] 线段，即结点 [l,r] 表示线段 [l−1,r] 。其实它们都一样，只是写起来不同。

#include
     
      using  namespace std;const double eps = 1e-9;#define rep(i,f,t) for(int i = (f),_end = (t); i <= _end; ++i)#define clr(c,x) memset(c,x,sizeof(c));#define MID int mid = (L+R)>>1;#define CHD int lc = node<<1,rc = node<<1|1;struct Node{    double x,y1,y2;    int from,to;    bool flag;    Node(double xx,double yy1,double yy2,bool f)        :x(xx),y1(yy1),y2(yy2),flag(f){}    bool operator< (const Node &n2) const{ return x < n2.x; }};vector
      
        vs;vector
       
         line;const int maxn = 202<<2;struct sgt{    int cov[maxn];    double len[maxn];    void init(){        clr(cov,0);        clr(len,0);    }    void maintain(int node,int L,int R){        if(cov[node]){            len[node] = vs[R]-vs[L-1];        }else if(L != R){            CHD;            len[node] = len[lc]+len[rc];        }else{            len[node] = 0;        }    }    double query(){        return len[1];    }    void update(int from,int to,int val,int node,int L,int R){        if(from <= L && R <= to){            cov[node] += val;        }else{            MID;CHD;            if(from <= mid)update(from,to,val,lc,L,mid);            if(to > mid) update(from,to,val,rc,mid+1,R);        }        maintain(node,L,R);    }}tree;bool equ(double x,double y){    return fabs(x-y)
       
      
     

版权声明：本文为博主原创文章，未经博主允许不得转载。