首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >HDU1542 Atlantis 线段树+扫描线

HDU1542 Atlantis 线段树+扫描线

作者头像
用户2965768
发布2019-05-09 16:43:39
3050
发布2019-05-09 16:43:39
举报
文章被收录于专栏:wymwym
#include <bits/stdc++.h>
using namespace std;
struct Line{
	int flag;
	double x,y1,y2;
	Line(){}
	Line(double a,double b,double c,int d)
	{
		x = a; y1 = b; y2 = c; flag = d;
	}
	bool operator < (const Line &t)const{
		return x<t.x;
	}
};
struct N{
	int lft,rit,flag;
	double ll,rr,len;
	int mid(){return (lft+((rit-lft)>>1));}
	void fun(int val){
		flag+=val;
		if(flag==0)len=0;
		else len=rr-ll;
	}
};
N node[1000];
vector<double> y;
vector<Line> line;
map<double,int> H;
void build(int l,int r,int id){
	node[id].lft = l; node[id].rit = r;
	node[id].flag = 0; node[id].len = 0;
	node[id].ll = y[l]; node[id].rr = y[r];
	if(l+1!=r){
		int mid = node[id].mid();
		build(l,mid,id*2);
		build(mid,r,id*2+1);
	} 
}
void update(int l,int r,int id,int val){
	int lf = node[id].lft, ri = node[id].rit;
	if(lf+1==ri)node[id].fun(val);//为两相邻(从小到大)长度边时 
	else{
		int mi = node[id].mid();
		if(l<mi)update(l,r,id*2,val);
		if(r>mi)update(l,r,id*2+1,val);
		node[id].len = node[id*2].len + node[id*2+1].len;
	}
}
int main()
{
	int n,t_cnt=0;
	while(scanf("%d",&n)&&n){
		H.clear(); line.clear(); y.clear();
		memset(node,0,sizeof(node));
		double x1,x2,y1,y2;
		for(int i=0;i<n;i++)
		{
			scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
			line.push_back(Line(x1,y1,y2,1));
			line.push_back(Line(x2,y1,y2,-1));
			y.push_back(y1); y.push_back(y2);
		}
		sort(line.begin(),line.end());
		sort(y.begin(),y.end());
		y.erase(unique(y.begin(),y.end()),y.end());
		
		for(int i=0;i<(int)y.size();i++)H[y[i]] = i;
		
		build(0,(int)y.size()-1,1);
		
		double ans = 0;
		printf("Test case #%d\n",++t_cnt);
		for(int i=0;i<(int)line.size();i++){//对每条扫描线
			if(i!=0)ans+=(line[i].x-line[i-1].x)*node[1].len;
			update(H[line[i].y1],H[line[i].y2],1,line[i].flag);
		}
		printf("Total explored area: %.2lf\n\n",ans);
	}
	return 0;
 } 
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2019年04月24日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档