覆盖的面积 hdu1255 扫描线+线段树

2019-11-06 08:57:25

字体：大中小

来源：转载

供稿：网友

题目大意

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

分析

介绍扫描线只要在统计的时候看看是否被覆盖两次就可以了

code

#include<iostream>#include<cstring>#include<cstdio>#include<cmath>#include<string>#include<algorithm>using namespace std;struct arr{ int x,y; long long lazy; long long sum; double small;}f[3000000];struct ae{ int x,y; double z; int flag;}line[10000],ver[10000];int line_m,ver_m;int h[10000];double l[10000];int n,m;double ans=0;int insert(int r,int x,int y,int add,double small)//线段树修改操作。{ if (f[r].x+1==f[r].y) { if (f[r].sum==1) f[r].small=small; f[r].sum+=(y-x)*add; f[r].lazy+=add; if ((f[r].sum==1)&&(add==-1)) ans+=(small-f[r].small)*(l[y]-l[x]); return 0; } int mid=(f[r].x+f[r].y)/2; if (y<=mid) insert(r*2,x,y,add,small); else if (x>=mid) insert(r*2+1,x,y,add,small); else insert(r*2,x,mid,add,small),insert(r*2+1,mid,y,add,small);}int maketree(int r,int x,int y)//建树{ f[r].x=x; f[r].y=y; f[r].lazy=0; f[r].sum=0; if ((x+1)==y) return 0; int mid=(x+y)/2; maketree(r*2,x,mid),maketree(r*2+1,mid,y);}inline int cmp(ae a,ae b){ return a.z<b.z;}int main(){ int T=0; scanf("%d",&T); while (T--){ scanf("%d",&n); memset(line,0,sizeof(line)); memset(ver,0,sizeof(ver)); maketree(1,1,10000); ans=0; line_m=0; ver_m=0; for (int i=1;i<=n;i++) { double x1,y1,x2,y2; scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); line[++line_m]=(ae){line_m,line_m+1,y1,1}; line[++line_m]=(ae){line_m,line_m-1,y2,-1}; ver[++ver_m]=(ae){ver_m,ver_m+1,x1,1}; ver[++ver_m]=(ae){ver_m-1,ver_m,x2,-1}; } sort(line+1,line+line_m+1,cmp); int cnt=1; h[line[1].x]=cnt; l[cnt]=line[1].z; for (int i=2;i<=line_m;i++) { if (line[i-1].z!=line[i].z) cnt++; h[line[i].x]=cnt; l[cnt]=line[i].z; } for (int i=1;i<=ver_m;i++) { ver[i].x=h[ver[i].x]; ver[i].y=h[ver[i].y]; } sort(ver+1,ver+ver_m+1,cmp); for (int i=1;i<=ver_m;i++) insert(1,ver[i].x,ver[i].y,ver[i].flag,ver[i].z); PRintf("%.2f/n",ans); } return 0;}

上一篇：Charles使用记录

下一篇：RTMP学习（二）RTMP规范简单分析

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注