HDU 1828 Picture （线段树+扫描线+离散化）

待我称王封你为后i 2022-06-12 06:27 210阅读 0赞

A number of rectangular posters, photographs and other pictures of the same shape are pasted on a wall. Their sides are all vertical or horizontal. Each rectangle can be partially or totally covered by the others. The length of the boundary of the union of all rectangles is called the perimeter.  
  
Write a program to calculate the perimeter. An example with 7 rectangles is shown in Figure 1.  
  
![ffc4743f5b88835b346a7d0f75aee63b_v_1500090712][]  
  
The corresponding boundary is the whole set of line segments drawn in Figure 2.  
  
![6017b88c9754532f0baeab1fdae631ee_v_1500090712][]  
  
The vertices of all rectangles have integer coordinates.

Input

Your program is to read from standard input. The first line contains the number of rectangles pasted on the wall. In each of the subsequent lines, one can find the integer coordinates of the lower left vertex and the upper right vertex of each rectangle. The values of those coordinates are given as ordered pairs consisting of an x-coordinate followed by a y-coordinate.  
  
0 <= number of rectangles < 5000  
All coordinates are in the range −10000,10000 −10000,10000 and any existing rectangle has a positive area.  
  
Please process to the end of file.

Output

Your program is to write to standard output. The output must contain a single line with a non-negative integer which corresponds to the perimeter for the input rectangles.

Sample Input

7
    -15 0 5 10
    -5 8 20 25
    15 -4 24 14
    0 -6 16 4
    2 15 10 22
    30 10 36 20
    34 0 40 16

Sample Output

228

题解：

hhhh先让我笑一会，我昨天看了一下午和晚上的扫描线，因为每个人的风格不同。。然后我就基本没看懂，所以打算自己专研一下，今天早上突然想到能不能用做矩形面积的方法稍加修改一下变成求周长！！然后第一遍wa了。。我抱着基本又会wa的心态修改了一点东西。。交上去，第二遍居然ac了，好兴奋啊，来写博客了，不过我用的是最笨的方法，就是扫两遍，所以消耗的时间是一般做法的两倍，不过还是31ms。。正常做法是15ms，完全在2000ms之内，而且写起来还比较简单比较好想，感觉完全套模板一样，记录一下

代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<deque>
    using namespace std;
    const int N=5555;
    struct edge
    {
        int l,r;
        int h;
        int d;
    };
    int cmp(edge x,edge y)//对边排序，高度小的在前，相同时，入边在前
    {
        if(x.h!=y.h)
        return x.h<y.h;
        return x.d>y.d;//这个很重要，我就是加上了这个就ac了
    }
    edge a[N*2];//由于最大有5000个矩形，所以最多有10000条边，a代表平行于x轴的扫描线
    edge b[N*2];//平行于y轴的扫描线
    struct node
    {
        int l,r;
        int s;//是否被完全覆盖
        int len;//覆盖长度
    };
    node t[N*8];//边数*4
    int y[N*2];//保存每条平行于y轴扫描线的纵坐标
    int x[N*2];//保存每条平行于x轴扫描线的横坐标
    void Build(int l,int r,int num)//日常建树
    {
        t[num].l=l;
        t[num].r=r;
        t[num].s=0;
        t[num].len=0;
        if(l==r)
            return;
        int mid=(l+r)/2;
        Build(l,mid,num*2);
        Build(mid+1,r,num*2+1);
    }
    void Pushup(int num,int x[])//合并子区间，向上传递状态，与求面积不同多加了参数x[]
    {
        if(t[num].s)//如果完全覆盖
        {
            t[num].len=x[t[num].r+1]-x[t[num].l];
        }
        else if(t[num].l==t[num].r)//为一个点
        {
            t[num].len=0;
        }
        else//不完全覆盖
        {
            t[num].len=t[num*2].len+t[num*2+1].len;
        }
    }
    void Update(int l,int r,int num,int d,int x[])//与求面积相比多加了x[]，d为边的性质
    {
        if(l==t[num].l&&r==t[num].r)
        {
            t[num].s+=d;
            Pushup(num,x);
            return;
        }
        int mid=(t[num].l+t[num].r)/2;
        if(r<=mid)
            Update(l,r,num*2,d,x);
        else if(l>mid)
            Update(l,r,num*2+1,d,x);
        else
        {
            Update(l,mid,num*2,d,x);
            Update(mid+1,r,num*2+1,d,x);
        }
        Pushup(num,x);
    }
    int main()
    {
        int i,j,k,n,tot;
        int s,x1,x2,y1,y2;
        while(scanf("%d",&n)!=EOF&&n)
        {
            tot=0;
            for(i=0;i<n;i++)
            {
                scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
                a[tot].l=x1;
                a[tot+1].l=x1;
                a[tot].r=x2;
                a[tot+1].r=x2;
                a[tot].h=y1;
                a[tot+1].h=y2;
                a[tot].d=1;
                a[tot+1].d=-1;
                x[tot]=x1;
                x[tot+1]=x2;
                b[tot].l=y1;
                b[tot+1].l=y1;
                b[tot].r=y2;
                b[tot+1].r=y2;
                b[tot].h=x1;
                b[tot+1].h=x2;
                b[tot].d=1;
                b[tot+1].d=-1;
                y[tot]=y1;
                y[tot+1]=y2;//一大长条都是记录边的性质，与求面积相比代码多了一倍，因为要记录两次
                tot+=2;
            }
            sort(a,a+tot,cmp);//对边排序
            sort(b,b+tot,cmp);
            sort(x,x+tot);//对端点排序，用于离散化去重
            sort(y,y+tot);
            k=unique(x,x+tot)-x;//去重
            Build(0,k-1,1);
            s=0;
            for(i=0;i<tot;i++)
            {
                int o=t[1].len;//o保存的是初始整个区间的覆盖状态
                int l=lower_bound(x,x+k,a[i].l)-x;//找到边的左右端点在x数组中的位置
                int r=lower_bound(x,x+k,a[i].r)-x-1;//-1于离散化有关，详情见我求矩形面积扫描线内容有讲
                Update(l,r,1,a[i].d,x);
                s+=abs(t[1].len-o);//好好想想，求外轮廓周长是不是和变化的长度有关
            }
            k=unique(y,y+tot)-y;//重复再做一遍求平行于y轴线的长度
            Build(0,k-1,1);
            for(i=0;i<tot;i++)
            {
                int o=t[1].len;
                int l=lower_bound(y,y+k,b[i].l)-y;
                int r=lower_bound(y,y+k,b[i].r)-y-1;
                Update(l,r,1,b[i].d,y);
                s+=abs(t[1].len-o);
            }
            printf("%d\n",s);
        }
    
    }

[ffc4743f5b88835b346a7d0f75aee63b_v_1500090712]: https://odzkskevi.qnssl.com/ffc4743f5b88835b346a7d0f75aee63b?v=1500090712
[6017b88c9754532f0baeab1fdae631ee_v_1500090712]: https://odzkskevi.qnssl.com/6017b88c9754532f0baeab1fdae631ee?v=1500090712