HDU 1255 覆盖的面积（线段树扫描线+面积交）-白红宇

HDU 1255 覆盖的面积（线段树扫描线+面积交）

阅读量：5823 次

发布时间：2019-06-18

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

　　自己YY了一个的写法，不过时间复杂度太高了，网上的想法太6了

　　题意：给你一些矩阵，求出矩阵的面积并

　　首先按照x轴离散化线段到线段树上（因为是找连续区间，所以段建树更加好做）。

然后我们可以想一下怎样才能使面积相交呢？我们可以注意到如果矩阵入线出现超过一次就一定有面积相交，所以我们记录入线与出线，再排序y轴，从小到大（注意y轴等大时先进后出）扫描线段。

　　记录：总长度，当前一整段一起覆盖一次的长度，当前一整段一起覆盖超过一次的长度，当前一整段一起覆盖覆盖的次数（注意这一整段的情况不会更新到孩子节点）为什么是当前一整段且不更新呢？因为我们要计算的是插入这一段（入线或出线）后，所有的线覆盖超过一次的长度。如果仅仅计算入线中超过一次线覆盖的长度，就会少计算一些面积，原因是我们每次会把y轴更新，这样就还有一些不在现在入线这一段中却覆盖超过一次的线段没有统计。

入线：矩阵下方的x轴的线（按照y轴扫描），表示矩阵进入扫描线，开始计算

出现：矩阵上方的x轴的线（按照y轴扫描），表示矩阵已经出去，不能计算了

/*给一些矩阵求矩阵面积交：离散化x轴，排序y轴扫描，注意记录一个cover，关键在此cover表示仅仅次一连续段的覆盖情况们不要更新到孩子节点而此时只需要记录区间覆盖两次及以上的长度是多少就好*/#include#include
      
       #include
       
        #include
        
         using namespace std;#define mul(a,b) (a<
         
          >b)const int Max=2010<<2;//每个矩形扫描时看做两条线struct node{    double len[3];//线段本身长度，覆盖次数为1次，覆盖次数大于1次的线段的长度    int cover;//表示这一段被覆盖的次数}segtr[Max];struct nide{    int typ;    double xx1,xx2,yy1;}lin[Max];map
          
            mp;//快速找到某个x所对应的树上的点double llin[Max];//离散化到树上对应节点bool cmp(struct nide p1,struct nide p2){ if(p1.yy1==p2.yy1) return p1.typ>p2.typ;//关键 同一个位置先进后出 return p1.yy1
           
            =2) { segtr[now].len[1]=0.0; segtr[now].len[2]=segtr[now].len[0]; } else if(segtr[now].cover==1)//此线段被覆盖一次，则孩子节点的线段覆盖情况就应该都加一次，注意此点与孩子节点的覆盖次数不相干 { if(sta+1!=enn) segtr[now].len[2]=segtr[next].len[2]+segtr[next|1].len[2]+segtr[next].len[1]+segtr[next|1].len[1]; else segtr[now].len[2]=0.0; segtr[now].len[1]=segtr[now].len[0]-segtr[now].len[2];//len 1+2 == 0 } else { if(sta+1==enn) { segtr[now].len[1]=0.0; segtr[now].len[2]=0.0; } else { segtr[now].len[1]=segtr[next].len[1]+segtr[next|1].len[1]; segtr[now].len[2]=segtr[next].len[2]+segtr[next|1].len[2]; } } return;}void Update(int sta,int enn,int now,int x,int y,int z){ if(sta>=x&&enn<=y) { segtr[now].cover+=z; Upnow(now,sta,enn);//更新len return; } int mid=dir(sta+enn,1); int next=mul(now,1); if(mid>x) Update(sta,mid,next,x,y,z); if(mid
            
             ::iterator it=mp.begin();it!=mp.end();++it) { it->second=cnt; llin[cnt++]=it->first; } cnt--;//注意不能多 printf("%.2f\n",Solve(m,cnt)); } return 0;}

转载于:https://www.cnblogs.com/zhuanzhuruyi/p/5863733.html

你可能感兴趣的文章