本文主要是介绍HDU 1255 扫描线，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
扫描线处理矩形覆盖过至少两次的区域的面积.
把callen函数的修改一下即可
data[k].len表示被覆盖的长度
data[k].sum表示被覆盖两次以上的长度
#include "stdio.h"
#include "string.h"
#include "algorithm"
#include "math.h"
using namespace std;struct Mark
{double x,ml,mr;int flag;
}mark[50010];struct Data
{double ml,mr,s,len,sum;int l,r,lazy;
}data[50010];double y[50010];bool cmp(Mark a,Mark b)
{return a.x-b.x<0.0000001;
}void build(int l,int r,int k)
{int mid;data[k].l=l;data[k].r=r;data[k].ml=y[l];data[k].mr=y[r];data[k].s=data[k].lazy=0;data[k].len=data[k].sum=0;if (l+1==r) return ;mid=(l+r)/2;build(l,mid,k*2);build(mid,r,k*2+1);
}void callen(int k)
{if (data[k].s>1){data[k].len=data[k].mr-data[k].ml;data[k].sum=data[k].mr-data[k].ml;}elseif (data[k].s==1){data[k].len=data[k].mr-data[k].ml;if (data[k].l+1==data[k].r) data[k].sum=0;elsedata[k].sum=data[k*2].len+data[k*2+1].len;}elseif (data[k].l+1==data[k].r){data[k].len=0;data[k].sum=0;}else{data[k].len=data[k*2].len+data[k*2+1].len;data[k].sum=data[k*2].sum+data[k*2+1].sum;}
}void updata(int k,Mark b)
{if (data[k].ml==b.ml && data[k].mr==b.mr){data[k].s+=b.flag;callen(k);return ;}if (b.mr<=data[k*2].mr) updata(k*2,b);elseif (b.ml>=data[k*2+1].ml) updata(k*2+1,b);else{Mark c;c=b;c.mr=data[k*2].mr;updata(k*2,c);c=b;c.ml=data[k*2+1].ml;updata(k*2+1,c);}callen(k);
}int main()
{int Case,n,i,len,cnt;double sum,x1,y1,x2,y2;scanf("%d",&Case);while (Case--){cnt=0;scanf("%d",&n);for (i=0;i<n;i++){scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);mark[cnt].x=x1;mark[cnt].ml=y1;mark[cnt].mr=y2;mark[cnt].flag=1;y[cnt++]=y1;mark[cnt].x=x2;mark[cnt].ml=y1;mark[cnt].mr=y2;mark[cnt].flag=-1;y[cnt++]=y2;}sort(mark,mark+cnt,cmp);sort(y,y+cnt);len=1;for (i=1;i<cnt;i++)if (y[i]!=y[i-1]){y[len++]=y[i];}len--;build(0,len,1);sum=0;updata(1,mark[0]);for (i=1;i<cnt;i++){sum+=data[1].sum*(mark[i].x-mark[i-1].x);updata(1,mark[i]);}printf("%.2lf\n",sum);}return 0;
}
这篇关于HDU 1255 扫描线的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
