hdu1255 覆盖的面积 线段树+里离散化求矩形面积的交

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1255

求矩形面积的交的线段树题目，刚做了求并的题目，再做这个刚觉良好啊，只要再加一个表示覆盖次数大于1次的长度变量即可

代码：

 #include<iostream>

 #include<cstdlib>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int maxn=;

 class node

 {

    public:

    int l,r;

    int c;

    double cnt;

    double more ;//表示被覆盖次数大于一次的长度

    double lf,rf;

 };

 node segTree[maxn*];

 class line

 {

     public:

     double x,y1,y2;

     int f;

 };

 line  le[maxn*];

 bool cmp(line a, line b)

 {

      return a.x< b.x;

 }

 double y[maxn*];

 void build(int num,int l, int r)

 {

         segTree[num].l=l;

         segTree[num].r=r;

         segTree[num].cnt=;

         segTree[num].more==;

         segTree[num].lf=y[l];

         segTree[num].rf=y[r];

         if(l+==r) return;

         int mid=(l+r)/;

         build(num*,l,mid);

         build(num*+,mid,r);

 }

 void calen(int num)

 {

       if(segTree[num].c >=)

       {

           segTree[num].more=segTree[num].cnt=segTree[num].rf-segTree[num].lf;

           return ;

       }

       else if(segTree[num].c==)

            {

              segTree[num].cnt=segTree[num].rf-segTree[num].lf;

              if(segTree[num].l+ ==segTree[num].r) segTree[num].more=;

              else segTree[num].more=segTree[num*].cnt+segTree[num*+].cnt;

            }

           else

            {

              if(segTree[num].l+ ==segTree[num].r )

               {

                 segTree[num].cnt=segTree[num].more=;

               }

              else

              {

                 segTree[num].cnt=segTree[num*].cnt+segTree[num*+].cnt;

                 segTree[num].more=segTree[num*].more+segTree[num*+].more;

              }

          }

 }

 void update(int num, line e)

 {

    if(e.y1 == segTree[num].lf && e.y2==segTree[num].rf)

    {

         segTree[num].c+=e.f;

         calen(num);

         return ;

    }

    if(e.y2 <= segTree[num*].rf) update(num*,e);

    else if(e.y1 >= segTree[num*+].lf) update(num*+,e);

    else

         {

             line temp=e;

             temp.y2=segTree[num*].rf;

             update(num*,temp);

             temp=e;

             temp.y1=segTree[num*+].lf;

             update(num*+,temp);

         }

         calen(num);

 }

 int main()

 {

     int t;

     int n;

     double x1,x2,y1,y2;

     scanf("%d",&t);

     while(t--)

     {

        scanf("%d",&n);

        int num=;

        for(int i=;i<=n;i++)

        {

           scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);

           le[num].x=x1;

           le[num].y1=y1;

           le[num].y2=y2;

           le[num].f=;

           y[num]=y1;

           num++;

           le[num].x=x2;

           le[num].y1=y1;

           le[num].y2=y2;

           le[num].f=-;

           y[num]=y2;

           num++;

        }

        sort(le+,le+num,cmp);

        sort(y+,y+num);

        build(,,num-);

        update(,le[]);

        double ans=;

        for(int i=;i<num;i++)

        {

             ans+=segTree[].more*(le[i].x - le[i-].x);

             update(,le[i]);

        }

        printf("%.2lf\n",ans);

     }

     return ;

 }

hdu1255 覆盖的面积 线段树+里离散化求矩形面积的交的相关教程结束。