扫描线处理矩形覆盖过至少两次的区域的面积.
把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;}
，少一点预设的期待，那份对人的关怀会更自在
