POJ1389:Area of Simple Polygons——扫描线线段树题解+全套代码注释

时间:2021-06-15 22:08:00

http://poj.org/problem?id=1389

题面描述
在二维xy平面中有N,1 <= N <= 1,000个矩形。矩形的四边是水平或垂直线段。矩形由左下角和右上角的点定义。每个角点都是一对两个非负整数,范围从0到50,000,表示其x和y坐标。

求出所有矩形的面积(重叠部分只算一次)

示例:考虑以下三个矩形:

矩形1:<(0,0)(4,4)>,

矩形2:<(1,1)(5,2)>,

矩形3:<(1,1)(2,5)>。

所有由这些矩形构造的简单多边形的总面积为18。

输入
输入由多个测试用例组成。一行4 -1分隔每个测试用例。一个额外的4 -1的行标志着输入的结束。在每个测试用例中,矩形都是一行一个地排列的。在矩形的每一行中,给出4个非负整数。前两个是左下角的x和y坐标。接下来的两个是右上角的x和y坐标。

输出
对于每个测试用例,输出所有简单多边形的总面积。

示例输入
0 0 4 4
1 1 5 2
1 1 2 5
-1 -1 -1 -1
0 0 2 2
1 1 3 3
2 2 4 4
-1 -1 -1 -1
-1 -1 -1 -1

示例输出
18
10

 

线段树的妙用之一——扫描线。

我们先将坐标离散化(然而这题数据小,不需要)

然后将一个矩形分成两半,存下它的下边界和上边界,并且用w记录哪个是上边界哪个是下边界。

这里先将上边界w=-1,下边界w=1(下面说为什么)

然后我们按照每个边界的y从小到大排序(如果y相同,先添加上界)。

这样预处理就完成了。

完后开始想线段树的含义。

节点表示其区间内被覆盖的点(不算重复)的数目。

那么我们假设一条边的长度为k,那么其覆盖的点的数量就是看k+1,于是为了方便起见,我们把边界都少存一位,这样我们就可以用这个表示边界长度了。

然后我们一条一条添加边,等效于在线段树区间内+w。

现在你知道为什么上边界w=-1了:标志着这个矩形结束了,就是把原来被覆盖的点撤回。

那么显然从上一个边界到下一个边界中矩形覆盖的面积就是tree[1]*上下边界距离。

把他们都加在一起就是答案,这样做是不是很巧妙的避免了重复面积啊(原因是被覆盖的点没有被重复计算)!

但是这样问题就变成了如何求被覆盖的点(不算重复)的数目了。

我们用lazy标记表示当前区间被一整条下边界完全经过,这样的边的边数。

如果lazy>0说明该区间被完全覆盖了。

如果lazy=0:

如果此时l=r,直接更新为0(显然)。

如果不是,我们就需要重新更新节点的值了,那就是他的左右儿子的节点个数和。

(思考lazy=0只是说明了该区间没有被完全覆盖,但是它可能被非完全经过的下边界覆盖了)

 

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
inline int read(){
    int X=0,w=1; char ch=0;
    while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();
    return X*w;
}
struct node{
    int y;
    int x1;
    int x2;
    int w;
}edge[2001];
bool cmp(node a,node b){
    return a.y<b.y;
}
int tree[200001];//区间被覆盖点数
int lazy[200001];//当前区间被一整条下边界完全经过,这样的边的边数
void build(int a,int l,int r){
    lazy[a]=0;
    if(l==r){
    tree[a]=0;
    return;
    }
    int mid=(l+r)>>1;
    build(a*2,l,mid);
    build(a*2+1,mid+1,r);
    tree[a]=tree[a*2]+tree[a*2+1];
    return;
}
void add(int a,int l,int r,int l1,int r1,int w){
    if(r1<l||l1>r)return;
    if(l1<=l&&r<=r1){
    lazy[a]+=w;
    if(lazy[a]>0)tree[a]=r-l+1;//完全覆盖,值为区间长 
    else if(l==r)tree[a]=0;//该点没有被覆盖,清零 
    else tree[a]=tree[a*2]+tree[a*2+1];//没有被完全覆盖,需要重新更新
    return;
    }
    int mid=(l+r)>>1;
    add(a*2,l,mid,l1,r1,w);
    add(a*2+1,mid+1,r,l1,r1,w);
    if(lazy[a]==0)tree[a]=tree[a*2]+tree[a*2+1];//没有被完全覆盖,需要重新更新
    return;
}
int main(){
    bool ok=0;
    while(233){
    int n=0;
    while(233){
        int a=read();
        int b=read();
        int c=read();
        int d=read();
        if(a==b&b==c&&c==d&&a==-1){
        if(!n)ok=1;
        break;
        }
        n++;
        edge[n*2-1].x1=a;
        edge[n*2-1].y=b;
        edge[n*2-1].x2=c;
        edge[n*2].y=d;
        edge[n*2-1].w=1;//到下界时加上该矩形
        edge[n*2].w=-1;//到上界时去掉该矩形
        edge[n*2].x1=edge[n*2-1].x1;
        edge[n*2].x2=edge[n*2-1].x2;
    }
    if(ok==1)break;
    sort(edge+1,edge+2*n+1,cmp);
    //根据上下界大小排序,从下往上扫描矩形 
    build(1,0,50000);
    ll h,ans=0;
    add(1,0,50000,edge[1].x1+1,edge[1].x2,edge[1].w);
    //建一个底 
    //因为是点数和,所有求长度的话要减去一个点就为长度 
    for(int i=2;i<=2*n;i++){
        h=edge[i].y-edge[i-1].y;//下一个矩形的下界(或者刚才的矩形的上界)之差即为高 
        ans+=h*tree[1];//底乘高为面积 
        add(1,0,50000,edge[i].x1+1,edge[i].x2,edge[i].w);//加上新矩形(或减去旧矩形) 
    }
    printf("%lld\n",ans);
    }
    return 0;
}