HDU 1255 (覆盖的面积) 典型的求交面积

spoiler posted @ 2011年4月10日 23:56 in ACM经典题目之线段树 , 1516 阅读

题目大意:给对角线 求覆盖次数至少为2次的面积

思路:首先把Y离散化,从小到大排序,然后以Y在数组种存放的位置,建树。但是线段树的lf,rf,存放的是Y的实际值,这就是离散化。

然后 在节点里用cover记录被覆盖的次数,lenth表示至少被覆盖一次的区间长度,inlenths,记录被覆盖两次以上的区间长度,这里比起求矩形的并面积,就是多了个记录与更新至少覆盖两次的情况的操作!
建树:跟求区间的并 区别不大,就是多了一个对inlenths的初始化。

更新:从上到下遍历,找到需要更新区间,如果是矩形的左边,cover加1,表示在这个高度,多了个区间覆盖在其之上,如果是矩形的右边则减1,说明,少了个区间覆盖在这个高度范围内,也就是矩形的覆盖,更新当前区间的lenth,如果cover>0则lenth等于该区间的整体长度,否则等于左右子树的覆盖长度,然后更新inlenths的长度,当cover>2,表明这个高度有2个以上矩形覆盖,即把inlenths赋值为当前区间的整体长度,如果cover=1说明这个区间整体只被覆盖一次,那么inlenths的值就等于左右子区间被覆盖一次以上的长度,因为整体的已经被覆盖了一次,只有子区间有被覆盖过大于等于一次,那么该长度也被覆盖了2次以上!,最后当cover=0,那么说明这个区间没有整体被覆盖过,那么inlenths等于左右子区间的inlenths的长度!最后结束这次的遍历。如果没有到达更新区间,那么就分三种情况,在左子树,右子树,左右子树混合的情况,分别考虑,然后每次都会往上更新lenth和inlenths的值!

源程序代码+部分注释:

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<algorithm>
#define esp (1e-8)
using namespace std;
double x_1,y_1,x_2,y_2,ym[30000],sum;
int i,j,n,cas;
struct tree{
	double lf,rf,lenth,inlenths;
	int cover;
}s[80000];
//这里数组开的小了当初,WA了好多次
//所以一气之下开的很大!
struct node{
	double x,y1,y2;
	int flag;
}t[30000];

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

void inlen(int num){
	if(s[num].cover>1)//表示整个区间被覆盖次数大于等于2
		s[num].inlenths=s[num].rf-s[num].lf;
	else if(s[num].cover==1)
		s[num].inlenths=s[num+num].lenth+s[num+num+1].lenth;
                //整个区间只被覆盖一次,如果子区间有被覆盖大于等于1次,说明该子段的长度,
                //为被覆盖至少2次的长度
	else
		s[num].inlenths=s[num+num].inlenths+s[num+num+1].inlenths;
                //整个区间都没被覆盖,该区间覆盖2次以上的长度就等于
                //他左右子树被覆盖的长度的和
}

int cmp1(double a,double b){
	return a<b;
}

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

int Build(int x,int y,int num){
	s[num].lf=ym[x];
	s[num].rf=ym[y];
	s[num].cover=s[num].lenth=s[num].inlenths=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(fabs(s[num].lf-n.y1)<=esp&&fabs(s[num].rf-n.y2)<=esp){
		s[num].cover+=n.flag;
		len(num);
		inlen(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 sn=n;
		sn.y2=s[num+num].rf;
		modify(num+num,sn);
		sn=n;
		sn.y1=s[num+num+1].lf;
		modify(num+num+1,sn);
	}
	len(num);
	inlen(num);
}

int main(){
	scanf("%d",&cas);
	while(cas--){	
		sum=0;
		scanf("%d",&n);
		for(i=1,j=1;i<=n;i++,j+=2){
			scanf("%lf %lf %lf %lf", &x_1, &y_1, &x_2, &y_2);
			ym[j]=y_1;
			t[j].x=x_1;
			t[j].y1=y_1;
			t[j].y2=y_2;
			t[j].flag=1;
			ym[j+1]=y_2;
			t[j+1].x=x_2;
			t[j+1].y1=y_1;
			t[j+1].y2=y_2;
			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]);
		for(i=2;i<j;i++){
			sum+=s[1].inlenths*(t[i].x-t[i-1].x);
			modify(1,t[i]);
		}
		printf("%.2lf\n",sum);
              //在我的编译器上好像样例的答案为7.62但是可以过
              //我不知道有没有更好的办法能够四舍五入保留两位小数
	}
	return 0;

}

 

Avatar_small
xyz 说:
2015年7月08日 02:19

你好,我有一个问题需要请教一下,就是为什么当cover==0的时候lenth是左右子树的lenth的和呢?这里不是很明白,请指教,谢谢


登录 *


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