hdu 1542 Atlantis 扫描线:矩形面积并

文章来自  Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)


题目大意

给出矩形的左下端点和右上端点的坐标,求所有的矩形的面积的并。


题解

求矩形面积并是扫描线的基础经典问题。这篇blog是借助这个来介绍初步入门扫描线。

扫描线,顾名思义,就是一条上下扫描或者左右扫描的虚拟的自主创造的线。

在扫描线扫描到一条线段的时候,就进行操作。而这种操作常常是利用线段树这种数据结构来进行存储的。

在矩形面积的并这一个问题中,我们可以这样去把要计算的总的面积分为这样几个部分来看:

(图来自于别人的博客,实在是不想自己画图了QAQ)

我们可以看到,这个图就是按照扫描线来分区计算面积的。

我们每一次找到一条扫描线,就要维护当前在这条扫描线上(当然这里扫描线是向上扫的)所有的线段的覆盖总长(覆盖部分不再重复计算)。

然后我们用两条扫描线的高度差去乘前一条扫面先上的所有线段的覆盖总长,就是这两条扫描线与矩形围成的面积并。

对于扫描线的顺序,只需要把矩形的上下边去离散化排序以下就可以了。

于是我们剩下的任务就是维护当前扫描线上的线段覆盖总长。

由于x坐标可能会很大,我们一样要对x进行离散化,并且记录离散化后的元素对应的离散化前的元素。

然后我们可以类比前缀和的方式:

对于每一个矩形的下边,我们设这里的标记为+1,对于每一个矩形的上边,我们设这里的标记为-1

这里的标记就可以使用线段树来维护了(但是这里的标记并不需要下放,也不需要向上更新,这里的标记是用于记录这段区间线段是否被覆盖的)。

于是我们在线段树中维护两个变量,一个表示这段区间表示的线段是否被完全覆盖,另一个表示这段区间被覆盖的线段的总长。

在求被覆盖线段总长时,要分两种情况进行讨论:

1.当前区间表示的线段被完全覆盖:区间被覆盖的线段总长即为这段区间表示的线段总长。

2.当前区间表示的线段未被完全覆盖:当前区间被覆盖的线段的总长=其左区间被覆盖的线段的总长+其右区间被覆盖的线段的总长。

我们是一边更新一边统计答案,统计答案只需要每次答案加上总区间被覆盖的线段总长×两条扫描线之间的高度差。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
struct node
{
    double x1, x2, y1, y2; int id;
    node(double X1 = 0, double Y1 = 0, double X2 = 0, double Y2 = 0) { x1 = X1, y1 = Y1, x2 = X2, y2 = Y2; }
}p[maxn], x[maxn];

struct node2{
    int x1, x2, k; double h;
    node2(int X1 = 0, int X2 = 0, double H = 0, int K = 0) : x1(X1),x2(X2),h(H),k(K){};
}nod[maxn];
bool cmp(node a,node b){
    return a.x1 < b.x1;
}
bool cmp2(node2 a,node2 b){
    return a.h < b.h;
}
struct tree{
    int vis,l,r;
    double sum;
}tr[maxn<<2];
int n,cnt,tot;
double pid[maxn<<1];
double a,b,c,d;
void build(int now,int l,int r){
    tr[now].l = l;
    tr[now].r = r;
    tr[now].sum = tr[now].vis = 0;
    if(l == r)
        return;
    int mid = (l + r) >> 1;
    build(now<<1,l,mid);
    build(now<<1|1,mid+1,r);
    return;
}
void push_up(int now){
    if(tr[now].vis)
        tr[now].sum = pid[tr[now].r+1] - pid[tr[now].l];
    else
        tr[now].sum = tr[now<<1].sum + tr[now<<1|1].sum;
    return;
}
void update(int now,int l,int r,int k){
    if(tr[now].l >= l && tr[now].r <= r){
        tr[now].vis += k;
        push_up(now);
        return;
    }
    int mid = (tr[now].r + tr[now].l) >> 1;
    if(l <= mid)update(now<<1,l,r,k);
    if(r > mid)update(now<<1|1,l,r,k);
    push_up(now);
    return;
}
int cas = 0;
double ans;
int main(){
    while(scanf("%d",&n) && n != 0){
        cas++;
        ans = 0;
        tot = 2 * n;
        memset(tr,0,sizeof(tr));
        cnt = 0;
        for(int i = 1;i <= n;++i){
            scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
            p[i] = node(a,b,c,d);
            x[i] = node(a,0,0,0);
            x[i+n] = node(c,0,1,0);
            x[i].id = x[i+n].id = i;
        }
        sort(x+1,x+1+tot,cmp);
        x[0].x1 = -1;
        for(int i = 1;i <= tot;++i){
            if(x[i].x1 != x[i-1].x1)pid[++cnt] = x[i].x1;
            if(!x[i].x2)p[x[i].id].x1 = cnt;
            else p[x[i].id].x2 = cnt;
        }
        build(1,1,cnt);
        for(int i = 1;i <= n;++i){
            nod[i] = node2(p[i].x1,p[i].x2,p[i].y1,1);
            nod[i+n] = node2(p[i].x1,p[i].x2,p[i].y2,-1);
        }
        sort(nod+1,nod+tot+1,cmp2);
        for(int i = 1;i <= tot;++i){
            if(i != 1)ans += (nod[i].h - nod[i-1].h) * tr[1].sum;
            update(1,nod[i].x1,nod[i].x2-1,nod[i].k);
        }
        printf("Test case #%d\nTotal explored area: %.2lf\n\n",cas,ans);
    }
    return 0;
}   

Pre: No Post
Sign in to leave a comment.
No Leanote account ? Sign up now.
0 comments
Title - Artist
0:00