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

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

阅读量：4943 次

发布时间：2019-06-11

本文共 2299 字，大约阅读时间需要 7 分钟。

给定平面上若干矩形,求出被这些矩形覆盖过至少两次的区域的面积.

这里写图片描述

这题比hdu1542复杂一点点()，就是要求至少被覆盖两次。

其实也没复杂多少。在线段树维护的时候只需用

len[node][i] 表示

node 结点被覆盖至少

i 次的长度就好了。

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

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           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 "<
           
            <
            
              Pr;vector
             
               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
              
                line;bool equ(double a,double b){ return fabs(a-b)
               
                >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\n",ans); } return 0;}