首页 > 代码库 > 线段树扫描线 HDU 1542
线段树扫描线 HDU 1542
n个矩形 问他们覆盖的面积重复的就算一次
x数组存线段 然后根据横坐标排一下
z 线段树 l - r 就是1 ~ 2*n
#include<stdio.h> #include<algorithm> #include<string.h> using namespace std; #define MAXN 110 struct line { double x,y1,y2; int flag; }x[MAXN]; double y[MAXN<<1]; struct node { int l,r,cov; double x,y_up,y_down; }z[16*MAXN]; bool cmp(line a,line b) { return a.x<b.x; } void Build(int l,int r,int a) { z[a].l=l; z[a].r=r; z[a].cov=0; z[a].x=-1; z[a].y_down=y[l]; z[a].y_up=y[r]; if(l+1==r)//叶子节点 return ; int mid=(l+r)>>1; Build(l,mid,a<<1); Build(mid,r,a<<1|1);//这边是mid } double Insert(int l,int r,int ind,int a) { if(x[ind].y1>=z[a].y_up||x[ind].y2<=z[a].y_down) //在外面 return 0; if(l+1==r)//叶子节点 { if(z[a].cov>0) { double sum=(x[ind].x-z[a].x)*(z[a].y_up-z[a].y_down); z[a].x=x[ind].x; //这边要更新x z[a].cov+=x[ind].flag; return sum; } else { z[a].x=x[ind].x; z[a].cov+=x[ind].flag; return 0; } } double ans1,ans2; int mid=(l+r)>>1; ans1=Insert(l,mid,ind,a<<1); ans2=Insert(mid,r,ind,a<<1|1);//这边是mid return ans1+ans2; } int main() { int n,ca=1; while(scanf("%d",&n)!=EOF&&n) { int cnt=1; for(int i=1;i<=n;i++) { double x1,y1,x2,y2; scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); x[cnt].x=x1; x[cnt].y1=y1; x[cnt].y2=y2; x[cnt].flag=1; y[cnt]=y1; cnt++; x[cnt].x=x2; x[cnt].y1=y1; x[cnt].y2=y2; x[cnt].flag=-1; y[cnt]=y2; cnt++; } sort(y+1,y+cnt); sort(x+1,x+cnt,cmp); Build(1,cnt-1,1); double ans=0; for(int i=1;i<cnt;i++) { ans+=Insert(1,cnt-1,i,1); } printf("Test case #%d\n",ca++); printf("Total explored area: %.2lf\n\n",ans); } return 0; }
线段树扫描线 HDU 1542
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。