hdu1255 覆盖面积

it2022-05-06  6

hdu1255 覆盖面积

题意:求N个矩形中,求被覆盖至少俩次的面积和

分析:一开始以为用总面积减去面积并就可以了,可是想了想,当面积被覆盖了俩次以上,就漏减 了,所以只能老老实实算了。

具体方法跟求面积并十分类似,求面积并时,排完序之后,每次插入一条线段之后,求出整个区间当前被覆盖的总长度再乘以 前后俩条线段的水平距离;

而这道题目,每次插入一条线段之后,求整个区间当前被覆盖至少俩次的总长度再乘以水平距离,;

要求整个区间被覆盖至少俩次的总长度,只需在原有代码上添加几个更新而已,具体代码附了解释

#include<iostream> #include<algorithm> #define maxn 2222 using namespace std; struct node { double x,y1,y2; int s; node(double a=0,double b=0,double c=0,int d=0):x(a),y1(b),y2(c),s(d){} friend bool operator<(const node a,const node b) { return a.x<b.x; } }; node ss[maxn]; bool cmp(node a,node b) { return a.x<b.x; } double len[maxn<<2],inlen[maxn<<2]; int cnt[maxn<<2]; double map1[maxn]; void PushUp(int k,int s,int t) { if(cnt[k]) len[k]=map1[t+1]-map1[s]; else if(t==s) len[k]=0; else len[k]=len[k<<1]+len[k<<1 |1]; } void inPushUp(int k,int s,int t) { if(cnt[k]>=2)//若被覆盖了俩次以上,则inlen[k]等于区间长度 inlen[k]=map1[t+1]-map1[s]; else if(t==s)//叶节点,等于零 inlen[k]=0; else if(cnt[k]==1)//若该区间整体被覆盖过一次,则inlen[k]等于子区间被覆盖过一次的线段长度之和 inlen[k]=len[k<<1]+len[k<<1|1]; else inlen[k]=inlen[k<<1]+inlen[k<<1 |1];//若整体没被标记过,则inlen[k]等于子区间被覆盖过俩次的线段长度之和 } void update(int l,int r,int c,int s,int t,int k) { if(l<=s && t<=r) { cnt[k]+=c; PushUp(k,s,t); inPushUp(k,s,t); return ; } int kl=k<<1,kr=kl+1,mid=(s+t)>>1; if(l<=mid) update(l,r,c,s,mid,kl); if(r>mid) update(l,r,c,mid+1,t,kr); PushUp(k,s,t); inPushUp(k,s,t); } int Bin(double key,int n,double map1[]) { int l = 0 , r = n - 1; while (l <= r) { int mid = (l + r) >> 1; if (map1[mid] == key) return mid; if (map1[mid] < key) l = mid + 1; else r = mid - 1; } return -1; } int main() { double a,b,c,d; int n,T; scanf("%d",&T); while(T--) { scanf("%d",&n); int m=0; for(int i=0;i<n;i++) { scanf("%lf %lf %lf %lf",&a,&b,&c,&d); map1[m]=b; ss[m++]=node(a,b,d,1); map1[m]=d; ss[m++]=node(c,b,d,-1); } sort(map1,map1+m); sort(ss,ss+m); int k=1; for (int i = 1 ; i < m ; i ++) if (map1[i] != map1[i-1]) map1[k++] =map1[i]; memset(cnt , 0 , sizeof(cnt)); memset(len , 0 , sizeof(len)); memset(inlen , 0 , sizeof(inlen)); double ans=0.0; for(int i=0;i<m-1;i++) { int l = Bin(ss[i].y1 , k , map1); int r = Bin(ss[i].y2 , k , map1) - 1; if (l <= r) update(l , r , ss[i].s , 0 , k - 1, 1); ans+=inlen[1]*(ss[i+1].x-ss[i].x); } printf("%.2f\n",ans); } return 0; }

转载于:https://www.cnblogs.com/nanke/archive/2011/10/02/2198255.html

相关资源:数据结构—成绩单生成器

最新回复(0)