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++ ,