3044 矩形面积求并
题目描述 Description
输入n个矩形，求他们总共占地面积（也就是求一下面积的并）
输入描述 Input Description
可能有多组数据，读到n=0为止(不超过15组)
每组数据第一行一个数n，表示矩形个数(n<=100)
接下来n行每行4个实数x1,y1,x2,y1(0 <= x1 < x2 <= 100000;0 <= y1 < y2 <= 100000)，表示矩形的左下角坐标和右上角坐标
输出描述 Output Description
每组数据输出一行表示答案
样例输入 Sample Input
2 10 10 20 20 15 15 25 25.5 0
样例输出 Sample Output
180.00
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 210 using namespace std; struct node{ double l,r,h;int d; node(){} node(double l,double r,double h,int d):l(l),r(r),h(h),d(d){} bool operator < (const node &b)const{ return h<b.h; } }a[maxn]; int cnt[maxn*4],n; double sum[maxn*4],all[maxn]; void pushup(int l,int r,int k){ if(cnt[k])sum[k]=all[r+1]-all[l]; else if(l==r)sum[k]=0; else sum[k]=sum[k<<1]+sum[k<<1|1]; } void update(int opl,int opr,int opv,int l,int r,int k){ if(l>=opl&&r<=opr){ cnt[k]+=opv; pushup(l,r,k); return; } int mid=(l+r)>>1; if(opl<=mid)update(opl,opr,opv,l,mid,k<<1); if(opr>mid)update(opl,opr,opv,mid+1,r,k<<1|1); pushup(l,r,k); } int main(){ while(1){ scanf("%d",&n); if(n==0)return 0; double x1,x2,y1,y2; for(int i=1;i<=n;i++){ scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); a[i]=node(x1,x2,y1,1); a[i+n]=node(x1,x2,y2,-1); all[i]=x1;all[i+n]=x2; } n<<=1; sort(a+1,a+n+1); sort(all+1,all+n+1); int m=unique(all+1,all+n+1)-all-1; memset(cnt,0,sizeof(cnt)); memset(sum,0,sizeof(sum)); double ans=0; for(int i=1;i<n;i++){ int l=lower_bound(all+1,all+m+1,a[i].l)-all; int r=lower_bound(all+1,all+m+1,a[i].r)-all; if(l<r)update(l,r-1,a[i].d,1,m,1); ans+=sum[1]*(a[i+1].h-a[i].h); } printf("%.2lf ",ans); } return 0; }