矩形面积并

例题：hdu1542
题意：裸题

从下面往上扫，扫到一个矩形的下底，那么对这个矩形底所在的x的区间都加上1。如果是上底的话就要减去1。这样的效果就是如果一个区间对应的x都是大于0的，则对应上面的面积就是要加的。如果是0的话，这个区间上面没有要加的面积。线段树维护的就是x轴有多少大于0的区间的总长度，然后这个长度*当前这根线和下一条线的差值的绝对值就是每扫一下ans要加的值。自己模拟一下就很清楚了。

#include
using namespace std;#define lson rt<<1
#define rson rt<<1|1const int maxn=1e5+5;struct node
{double x1,x2,y,sta;node(){}node(double x1,double x2,double y,double sta):x1(x1),x2(x2),y(y),sta(sta){}bool operator <(const node &a)const{return y<a.y;}
}p[maxn<<1];//存线
double tree[maxn<<2];
int lazy[maxn<<2];//标识数组，判断x的区间是否有效
double ls[maxn];//lsx坐标的数组
void pushup(int rt,int l,int r)
{if(lazy[rt])tree[rt]=ls[r+1]-ls[l];//如果当前的区间已经是有效的，那么就直接加上这段的长度else if(l==r)tree[rt]=0;//如果是一个点，是没有长度的else tree[rt]=tree[lson]+tree[rson];//最后的情况就直接更新为左右儿子之和
}void updata(int rt,int l,int r,int x,int y,int sta)
{if(x<=l&&r<=y){lazy[rt]+=sta;//标识数组加上这条线的状态pushup(rt,l,r);return;}int mid=(l+r)>>1;if(x<=mid)updata(lson,l,mid,x,y,sta);if(y>=mid+1)updata(rson,mid+1,r,x,y,sta);pushup(rt,l,r);
}int main()
{int n;int ca=0;while(~scanf("%d",&n)&&n){double x1,x2,y1,y2;for(int i=1;i<=n;i++)//把每个矩形拆成上下两根水平方向线{scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);p[i]=node(x1,x2,y1,1);//如果一条线是矩形的底，把状态置为1p[n+i]=node(x1,x2,y2,-1);//是上底的话就置为-1ls[i]=x1,ls[i+n]=x2;//记录所有出现的x值}n<<=1;sort(p+1,p+1+n);//将所有横的线按照y值从小到大排序sort(ls+1,ls+1+n);//将x值从小到大排序int sz=unique(ls+1,ls+1+n)-ls-1;//得到有多少种x值，离散化。double ans=0;memset(tree,0,sizeof(tree));memset(lazy,0,sizeof(lazy));for(int i=1;i<n;i++){int l=lower_bound(ls+1,ls+1+sz,p[i].x1)-ls;//获得这条线的左端点int r=lower_bound(ls+1,ls+1+sz,p[i].x2)-ls;//获得这条线的右端点if(l<r)updata(1,1,sz,l,r-1,p[i].sta);//r-1是因为长度，如1    2    3，点有三个，但是间隔只有两个ans+=tree[1]*(p[i+1].y-p[i].y);}printf("Test case #%d\nTotal explored area: %.2f\n\n",++ca,ans);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！