首页 > 代码库 > HDU_1542 线段树离散化+扫描线 平面面积计算
HDU_1542 线段树离散化+扫描线 平面面积计算
也是很久之前的题目，一直没做
做完之后觉得基本的离散化和扫描线还是不难的，由于本题要离散x点的坐标，最后要计算被覆盖的x轴上的长度，所以不能用普通的建树法，建树建到r-l==1的时候就停止，表示某段而不是某点，同样，左子树和右子树要变成 L MID ， MID R
比如1-4子树就是 1-2,2-4。。。2-4再分成2-3,3-4.
然后就是经典的扫描线用法，对下边设标记为1，上边设标记为-1，每次求得x轴被覆盖的长度，乘以和下一条线段的距离（即矩形的高）即可
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define lson rt<<1,l,mid#define rson rt<<1|1,mid,rusing namespace std;const int N = 210;double d[N*N];int flag[N*N];int n;double X[N];struct node{ double l,r,y,f; bool operator < (const node &rhs) const{ return y<rhs.y; }}seg[N];void build(int rt,int l,int r){ flag[rt]=0; d[rt]=0; if (r-l<=1){ return; } int mid=(l+r)>>1; build(lson); build(rson);}void up(int rt,int l,int r){ if (flag[rt]>0){ d[rt]=X[r]-X[l]; } else { if (r-l==1) d[rt]=0; else d[rt]=d[rt<<1]+d[rt<<1|1]; }}void cover(int L,int R,double v,int rt,int l,int r){ //cout<<l<<" @@@ "<<r<<endl; if (L<=l && r<=R){ flag[rt]+=v; up(rt,l,r); return; } if (r-l<=1) return; int mid=(l+r)>>1; if (R<=mid) cover(L,R,v,lson); else if (L>mid) cover(L,R,v,rson); else { cover(L,R,v,lson); cover(L,R,v,rson); } up(rt,l,r);}int main(){ double xa,ya,xb,yb; int kase=0; while (scanf("%d",&n)!=EOF) { if (n==0) break; int cnt=1; for (int i=1;i<=n;i++){ scanf("%lf%lf%lf%lf",&xa,&ya,&xb,&yb); X[cnt]=xa; seg[cnt++]=(node){xa,xb,ya,1.0}; X[cnt]=xb; seg[cnt++]=(node){xa,xb,yb,-1.0}; } sort(X+1,X+cnt); sort(seg+1,seg+cnt); int tmp=1; for (int i=2;i<cnt;i++){ if(X[i]!=X[i-1]){ X[++tmp]=X[i]; } } build(1,1,tmp); double ans=0; for (int i=1;i<cnt-1;i++){ //cout<<seg[i].l<<" .. "<<seg[i].r<<endl; int l1=lower_bound(X+1,X+1+tmp,seg[i].l)-X; int l2=lower_bound(X+1,X+1+tmp,seg[i].r)-X; //cout<<l1<<" "<<l2<<" "<<X[l1]<<" "<<X[l2]<<endl; cover(l1,l2,seg[i].f,1,1,tmp); //cout<<d[1]<<endl; ans+=d[1]*(seg[i+1].y-seg[i].y); //cout<<ans<<endl; } printf("Test case #%d\n",++kase); printf("Total explored area: %.2lf\n",ans); puts(""); } return 0;}
HDU_1542 线段树离散化+扫描线 平面面积计算
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。