Picture 扫描线求周长

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.

Picture 扫描线求周长

The corresponding boundary is the whole set of line segments drawn in Figure 2.

Picture 扫描线求周长

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] and any existing rectangle has a positive area.

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

求多个长方形并的周长。

参考了大佬的博客：https://blog.****.net/tomorrowtodie/article/details/52048323

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int INF=1<<29;
const int maxn=20000;

struct edge//扫描线
{
    int l,r;//左右端点横坐标
    int h;//这条线的高度
    int f;//标记上边下边，上边为-1，下边为1
}e[maxn<<1];
struct node
{
    int l,r;//该节点代表线段的左右坐标
    int len;//这个区间被覆盖的长度
    int s;//表示这个区间被重复覆盖了几次
    bool lc,rc;//表示这个节点左右的两个端点是否被覆盖
    int num;//这个区间被多少条线段覆盖
}q[maxn<<2];
bool cmp(edge a,edge b)//高度从小到大排序
{
    return a.h<b.h;
}
void pushup(int rt)//区间合并
{
    if(q[rt].s)//整个区间都被覆盖
    {
        q[rt].len=q[rt].r-q[rt].l+1;
        q[rt].lc=q[rt].rc=1;
        q[rt].num=1;
    }
    else if(q[rt].l==q[rt].r)//一个点
    {
        q[rt].len=0;
        q[rt].lc=q[rt].rc=0;
        q[rt].num=0;
    }
    else//这个区间没有被完全覆盖，合并左右儿子的信息
    {
        q[rt].len=q[rt<<1].len+q[rt<<1|1].len;
        q[rt].lc=q[rt<<1].lc;
        q[rt].rc=q[rt<<1|1].rc;
        q[rt].num=q[rt<<1].num+q[rt<<1|1].num-(q[rt<<1].rc & q[rt<<1|1].lc);//如果左儿子的右端点和右儿子的左端点都被覆盖
    }
}
void build(int l,int r,int rt)
{
    q[rt].l=l,q[rt].r=r;
    q[rt].s=q[rt].len=0;
    q[rt].lc=q[rt].rc=q[rt].num=0;
    if(l==r)
        return ;
    int m=(q[rt].l+q[rt].r)>>1;
    build(l,m,rt<<1);
    build(m+1,r,rt<<1|1);
}
void update(int C,int l,int r,int rt)
{
    if(l==q[rt].l&&r==q[rt].r)
    {
        q[rt].s+=C;
        pushup(rt);
        return ;
    }
    int m=(q[rt].l+q[rt].r)>>1;
    if(r<=m)
        update(C,l,r,rt<<1);
    else if(l>m)
        update(C,l,r,rt<<1|1);
    else
    {
        update(C,l,m,rt<<1);
        update(C,m+1,r,rt<<1|1);
    }
    pushup(rt);
}
int main()
{
    int n;
    cin>>n;
    int cnt=0;
    int x1,y1,x2,y2;
    int maxx=-INF;
    int minn=INF;
    for(int i=0;i<n;i++)
    {
        cin>>x1>>y1>>x2>>y2;
        maxx=max(maxx,max(x1,x2));
        minn=min(minn,min(x1,x2));
        e[cnt].l=e[cnt+1].l=x1;
        e[cnt].r=e[cnt+1].r=x2;
        e[cnt].h=y1;
        e[cnt+1].h=y2;
        e[cnt].f=1;e[cnt+1].f=-1;
        cnt+=2;
    }
    sort(e,e+cnt,cmp);
    int p=0;//上一次总区间覆盖的长度
    int ans=0;//周长
    build(minn,maxx,1);
    for(int i=0;i<cnt;i++)
    {
        update(e[i].f,e[i].l,e[i].r-1,1);
        //横线：现在总区间被覆盖的程度和上一次总区间被覆盖的长度的差的绝对值
        ans+=abs(q[1].len-p);
        //竖线：（下一条横线的高度-现在这条横线的高度）*2*目前总区间覆盖的线段的条数
        ans+=(e[i+1].h-e[i].h)*2*q[1].num;
        p=q[1].len;//每次更新上一次总区间覆盖的长度
    }
    cout<<ans<<endl;
    return 0;
}

Picture 扫描线求周长

相关推荐