HDU-1255 覆盖的面积（线段树扫描线+离散化+改进后超快的算法）

淡淡的烟草味﹌ 2022-06-10 10:40 122阅读 0赞

给定平面上若干矩形,求出被这些矩形覆盖过至少两次的区域的面积.  
  
![d1adc6253c233d9968f03fe1d872f86d_v_1502769328][]

Input

输入数据的第一行是一个正整数T(1<=T<=100),代表测试数据的数量.每个测试数据的第一行是一个正整数N(1<=N<=1000),代表矩形的数量,然后是N行数据,每一行包含四个浮点数,代表平面上的一个矩形的左上角坐标和右下角坐标,矩形的上下边和X轴平行,左右边和Y轴平行.坐标的范围从0到100000.  
  
注意:本题的输入数据较多,推荐使用scanf读入数据.

Output

对于每组测试数据,请计算出被这些矩形覆盖过至少两次的区域的面积.结果保留两位小数.

Sample Input

2
    5
    1 1 4 2
    1 3 3 7
    2 1.5 5 4.5
    3.5 1.25 7.5 4
    6 3 10 7
    3
    0 0 1 1
    1 0 2 1
    2 0 3 1

Sample Output

7.63
    0.00

题解：

这题我之前用区间单点暴力的做法1500ms过的，很不甘心，今天上午研究了几个人的写法，后来发现有一种很巧妙的思想，就是我们在扫描线模板的基础上，每一个节点保存的数据为2个，一个为覆盖一次的长度，另一个为覆盖两次以上的长度，那么我们每次更新两个长度，先更新len1，如果完全覆盖就赋全值，如果为一个点就为0，如果都不是就为子区间len1长度和，然后更新len2，如果覆盖两次赋权值，为点就为0，覆盖一次就改成子区间的len1和，其余情况为子区间len2和，然后其他和基本扫描线做法是一样了，还有就是答案依然要加上一个玄学控制精度的eps，这个做法速度可以达到190ms左右速度

附上之前的比较暴力的做法博客：[http://blog.csdn.net/qq\_37497322/article/details/77255966][http_blog.csdn.net_qq_37497322_article_details_77255966]

代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<vector>
    #include<deque>
    using namespace std;
    #define lson k*2
    #define rson k*2+1
    #define M (t[k].l+t[k].r)/2
    #define INF 1008611111
    #define ll long long
    #define eps 1e-15
    struct node
    {
        int l,r;
        double len1;//覆盖一次的长度
        double len2;//覆盖两次长度
        int v;//记录覆盖次数
    }t[2005*4];
    double xx[2005];//离散化后的数组
    void Build(int l,int r,int k)
    {
        t[k].l=l;
        t[k].r=r;
        t[k].len1=0;
        t[k].len2=0;
        t[k].v=0;
        if(l==r)
            return;
        int mid=M;
        Build(l,mid,lson);
        Build(mid+1,r,rson);
    }
    void pushup1(int k)//更新len1
    {
        if(t[k].v>0)
        {
            t[k].len1=xx[t[k].r+1]-xx[t[k].l];
            return;
        }
        else if(t[k].l==t[k].r)
        {
            t[k].len1=0;
        }
        else
        {
            t[k].len1=t[lson].len1+t[rson].len1;
        }
    }
    void pushup2(int k)//更新len2
    {
        if(t[k].v>1)
        {
            t[k].len2=xx[t[k].r+1]-xx[t[k].l];
            return;
        }
        if(t[k].l==t[k].r)
        {
            t[k].len2=0;
        }
        else if(t[k].v==1)
        {
            t[k].len2=t[lson].len1+t[rson].len1;
        }
        else
        {
            t[k].len2=t[lson].len2+t[rson].len2;
        }
    }
    void update(int l,int r,int k,int d)
    {
        if(l==t[k].l&&t[k].r==r)
        {
            t[k].v+=d;
            pushup1(k);
            pushup2(k);
            return;
        }
        int mid=M;
        if(r<=mid)
            update(l,r,lson,d);
        else if(l>mid)
            update(l,r,rson,d);
        else
        {
            update(l,mid,lson,d);
            update(mid+1,r,rson,d);
        }
        pushup1(k);
        pushup2(k);
    }
    struct edge//存扫描线
    {
        double l,r;
        double h;
        int d;//存扫描线性质，1为下底，-1为上底
    }a[2005];
    int cmp(edge x,edge y)//按高度从小到大排序
    {
        if(x.h!=y.h)
            return x.h<y.h;
        return x.d<y.d;
    }
    int main()
    {
        int i,j,k,n,tot,l,r,test,ans;
        double x1,x2,y1,y2;
        scanf("%d",&test);
        while(test--)
        {
            scanf("%d",&n);
            tot=0;
            for(i=0;i<n;i++)
            {
                scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
                a[tot].l=x1;
                a[tot].r=x2;
                a[tot].h=y1;
                a[tot].d=1;
                a[tot+1].l=x1;
                a[tot+1].r=x2;
                a[tot+1].h=y2;
                a[tot+1].d=-1;
                xx[tot]=x1;
                xx[tot+1]=x2;
                tot+=2;
            }
            sort(xx,xx+tot);
            sort(a,a+tot,cmp);
            ans=unique(xx,xx+tot)-xx;//离散化去重
            Build(0,ans-1,1);
            double s=0.0;
            int l=lower_bound(xx,xx+ans,a[0].l)-xx;
            int r=lower_bound(xx,xx+ans,a[0].r)-xx-1;
            update(l,r,1,a[0].d);
            for(i=1;i<tot;i++)
            {
                s+=(t[1].len2*(a[i].h-a[i-1].h));
                l=lower_bound(xx,xx+ans,a[i].l)-xx;
                r=lower_bound(xx,xx+ans,a[i].r)-xx-1;
                update(l,r,1,a[i].d);
            }
            printf("%.2lf\n",s+eps);//玄学
        }
        return 0;
    }

[d1adc6253c233d9968f03fe1d872f86d_v_1502769328]: https://odzkskevi.qnssl.com/d1adc6253c233d9968f03fe1d872f86d?v=1502769328
[http_blog.csdn.net_qq_37497322_article_details_77255966]: http://blog.csdn.net/qq_37497322/article/details/77255966