HDU 1542 Atlantis(线段的树应用——求矩形的面积并)

spoiler posted @ 2011年4月10日 15:59 in ACM经典题目之线段树 , 3008 阅读

题目大意:给定每个矩形的对角线的两个端点,让你求这些矩形的面积的并集,即重叠的不能重复计算!

题目分析:这题就是典型的线段树求面积并!

离散化:对所有节点的Y进行升序排序,然后以Y的位置建树,就是指,在线段树里面,左右节点的实际意义就是指这个线段在Y的升序数组里的位置,但是我们把lf,rf赋值为这个线段左右端点的具体值!这就是离散化!

建树的细节:树的每个节点有lf,rf,cover,lenth,分别指这个节点所表示的线段的左端点,右端点,被覆盖的次数(在这里覆盖的次数是为了 区分重叠矩形的情况下,高度的正确存取,因为一个矩形对Y轴的覆盖是以他的左边开始,右边结束的,所以当插入左边的时候,我们把cover+1,右边的时候把cover-1,说明这个矩形对Y的覆盖已经结束,计算下一个矩形时,不会错误的把我这个矩形的高度当作下一个矩形的高度!),lenth指这个区间被矩形覆盖的长度即矩形的实际高度!;

插入的时候,先把存放节点的数组,对X进行升序排序!然后顺次插入,分别计算!

代码如下+部分注释:

#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;

struct tree{
	double lf,rf,lenth;
	int cover;
}s[4000];//树节点定义

double x1,y1,x2,y2,ym[1000];

struct node{
	double x,y1,y2;
	int flag;
}t[4000];//存放矩形左,右边的节点

int cmp1(double x,double y){
	return x<y;
}

int cmp2(struct node a,struct node b){
	return a.x<b.x;
}

void len(int n){
	if(s[n].cover>0)
		s[n].lenth=s[n].rf-s[n].lf;
	else
		s[n].lenth=s[2*n+1].lenth+s[2*n].lenth;
}

int Build(int x,int y,int num){
	s[num].lf=ym[x];
	s[num].rf=ym[y];
	s[num].lenth=s[num].cover=0;
	if(x+1==y)
		return 0;
	int mid=(x+y)/2;
	Build(x,mid,num+num);
	Build(mid,y,num+num+1);
}

int modify(int num,struct node n){
	if(s[num].lf==n.y1&&s[num].rf==n.y2){
		s[num].cover+=n.flag;
		len(num);
		return 0;
	}
	if(n.y1>=s[num+num].rf)
		modify(num+num+1,n);
	else if(n.y2<=s[num+num+1].lf)
		modify(num+num,n);
	else{
		struct node vs=n;
		vs.y2=s[num+num].rf;
		modify(num+num,vs);
		vs=n;
		vs.y1=s[num+num+1].lf;
		modify(num+num+1,vs);
	}
	len(num);//往上更新线段被覆盖的实际长度!如果节点的cover>0 该区间节点的被覆盖就是,区间的整体程度,否则,该区间节点的被覆盖等于左右节点被覆盖长度的和!
}

int main(){
	int cas,i,j,k=1;
	double sum;
	while(cin>>cas,cas){
		for(j=i=1;i<=cas;i++,j+=2){
			scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
			ym[j]=y1;
			t[j].x=x1;
			t[j].y1=y1;
			t[j].y2=y2;
			t[j].flag=1;
			ym[j+1]=y2;
			t[j+1].x=x2;
			t[j+1].y1=y1;
			t[j+1].y2=y2;
			t[j+1].flag=-1;
		}
		sort(ym+1,ym+j,cmp1);
		sort(t+1,t+j,cmp2);
		Build(1,j-1,1);
		modify(1,t[1]);
		sum=0;
		for(i=2;i<j;i++){
			sum+=(t[i].xt[i-1].x)*s[1].lenth;
                      //每插入完一个点,就以他后继的点求面积!
			modify(1,t[i]);
		}
		printf("Test case #%d\n",k);
		printf("Total explored area: %.2lf\n\n",sum);
		k++;
	}
	return 0;
}

 

Avatar_small
夜 说:
2011年7月08日 15:32

sum+=(t[i].xt[i-1].x)*s[1].lenth;
这里貌似少个了减号。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter