codves  3044 矩形面积求并

 题目等级 : 钻石 Diamond

题目描述 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

210 10 20 2015 15 25 25.50

样例输出 Sample Output

180.00 线段树+扫描线 本题解析参照黄学长博客

#include
            
             #include
             
              #include
              
               using namespace std;int n,opl,opr,flag;int col[801];double hash[201],sum[1601],ans;struct node{    double x1,x2,h;    int f;}e[202];bool cmp(node a,node b) {
          return a.h
               
                =opl&&r<=opr)    {        col[k]+=flag;         up(k,l,r);        return;    }    int m=l+r>>1;    if(opl<=m) change(k<<1,l,m);    if(opr>m) change((k<<1)+1,m+1,r);    up(k,l,r);}int main(){    while(scanf("%d",&n)!=EOF)    {        if(!n) return 0;        double x1,y1,x2,y2;        for(int i=1;i<=n;i++)        {            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);            e[i*2-1].x1=e[i*2].x1=x1;            e[i*2-1].x2=e[i*2].x2=x2;            e[i*2-1].h=y1;e[i*2].h=y2;            hash[i*2-1]=x1;hash[i*2]=x2;            e[i*2-1].f=1;e[i*2].f=-1;        }        sort(hash+1,hash+2*n+1);        sort(e+1,e+2*n+1,cmp);        ans=0;        for(int i=1;i<=2*n;i++)        {            opl=lower_bound(hash+1,hash+2*n+1,e[i].x1)-hash;            opr=lower_bound(hash+1,hash+2*n+1,e[i].x2)-hash-1;            flag=e[i].f;            change(1,1,2*n);            ans+=sum[1]*(e[i+1].h-e[i].h);        }        printf("%.2lf\n",ans);    }}