当前位置:编程学习 > C/C++ >>

hdu 1542

离散化+扫描线+线段树。 虽然这题直接离散化也能过,但想要学习一下线段树求矩形并,就网搜各种线段树求矩形并的方法。其实做法还是跟离散化的做法差不多。

先介绍离散化+扫描线的做法(这种情况适应矩形数目不是很多的时候):

1,将矩形的四条边无限延长,则将平面区域分为了多个小矩形区域。我们要求的区域面积就是其中一些的小矩形的面积的和。(这一步只是理解,无实际操作)

2,分别将上述水平的划分线和竖直的划分线按从小到大排序。

3,对于输入的每个矩形,枚举每个x轴断点,再枚举每个y轴断点,判断每个小矩形是否在当前矩形中,是的话就记录record[i][j]=1否则为0; 然后用record[i][j[乘以小矩形的面积并累加;


下面介绍线段树的做法:

1,2步同上;

3,我们所说的线段树是对x轴建树。我们的理解中用y轴的平行线划分矩形。然后对于每个输入的矩形我们把它的上下两条边记录下来(包括这条边两个端点的x轴坐标,高度,上边或者下边等信息)。依次从高度小的边开始,把这条边对应的x轴区域在线段树中覆盖。当然这里矩形的下边是覆盖,上边是删除。 每插入一条边后由于pushup的作用,sum【1】记录了当前边插入后整个x轴被覆盖的长度。然后用这条边所在的直线与紧邻它的上一条水平直线间的距离乘以sum【1】就是被夹在这两条水平线间的面积。不断累加就可以了;


思路大概是这样,但还有一些细节问题需要注意。详见代码。


[cpp] 
#include<stdio.h> 
#include<math.h> 
#include<algorithm> 
#include<string.h> 
#define maxn 1000 
#define lson l , m , rt << 1 
#define rson m + 1 , r , rt << 1 | 1 
using namespace std; 
typedef struct 

    double l,r,h; int s;  // s用来记录这条边是上边还是下边 
}Seg; 
Seg ss[maxn]; 
 
 
int cnt[4*maxn]; double sum[4*maxn];  // cnt用来记录线段树中节点所对应的区间被覆盖的次数,sum记录覆盖的区间长度 
double X[maxn]; 
 
int Cmp(  Seg aa, Seg bb) 

    return aa.h < bb.h; 

 
int Bin( double key ,int n) 

    int l=1,r=n,m; double eps=1e-7; 
    while( l <= r ) 
    { 
        m=(l+r)/2; 
        if( fabs(X[m]-key) < eps )  return m; 
        if( X[m] < key ) l=m+1; 
        else  r=m-1; 
    } 
    return -1; 

 
void update(int a,int b,int c,int l,int r,int rt) 

    if( l==a && r==b ) 
    { 
        cnt[rt]+=c; 
        if( cnt[rt] ) sum[rt]=X[r+1]-X[l]; 
        else if (l == r) sum[rt] = 0; 
        else sum[rt]=sum[rt<<1]+sum[rt<<1|1]; 
        return ; 
    } 
    int m=(l+r)/2; 
    if( b<=m ) update(a,b,c,l,m,rt<<1); 
    else if( a>m ) update(a,b,c,m+1,r,rt<<1|1); 
    else 
    { 
        update(a,m,c,l,m,rt<<1); 
        update(m+1,b,c,m+1,r,rt<<1|1); 
    } 
    if( cnt[rt] ) sum[rt]=X[r+1]-X[l]; 
    else if (l == r) sum[rt] = 0; 
    else sum[rt]=sum[rt<<1]+sum[rt<<1|1]; 

 
int main() 

    int i,j,n,k,len,cas=1; double a,b,c,d; 
    while( scanf("%d",&n) , n ) 
    { 
        k=1; 
        for(i=1;i<=n;i++) 
        { 
            scanf("%lf%lf%lf%lf",&a,&b,&c,&d); 
            X[k]=a; ss[k].l=a; ss[k].r=c ; ss[k].h=b; ss[k].s=1; 
            k++; 
            X[k]=c; ss[k].l=a; ss[k].r=c ; ss[k].h=d; ss[k].s=-1; 
            k++; 
        } 
        sort(X+1,X+k); 
        sort(ss+1,ss+k,Cmp); 
        len=2; 
        for(i=2;i<k;i++)  //  x轴去重 
            if( X[i]!=X[i-1] )  X[len++]=X[i]; 
        double ret=0.0; 
        memset(sum,0,sizeof(sum)); memset( cnt,0,sizeof(cnt)); 
        for(i=1;i<k;i++) 
        { 
            int l = Bin( ss[i].l , len-1 ); 
            int r = Bin( ss[i].r , len-1)-1 ;     //  这里要注意-1 
            if( l<=r ) update( l,r,ss[i].s,1,len-2,1);  //这里线段树中的节点不是对应线段的断点,而是对应此端点到后面一个端点的线段,所以上面求出的r要减1 
            ret+= sum[1]*(ss[i+1].h-ss[i].h); 
        } 
        printf("Test case #%d\nTotal explored area: %.2lf\n\n",cas++,ret); 
    } 
    return 0; 

 

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,