专栏首页wymHDU1542 Atlantis 线段树+扫描线

HDU1542 Atlantis 线段树+扫描线

#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;
 } 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HDU 3018 Ant Trip(欧拉回路)

    #include <bits/stdc++.h> using namespace std; const int N=100005; int f[N]; ...

    用户2965768
  • Educational Codeforces Round 67 (Rated for Div. 2) A~E 贪心,构造,线段树,树的子树

    Educational Codeforces Round 67 (Rated for Div. 2)

    用户2965768
  • bzoj 2120 数颜色 带修莫队

    用户2965768
  • 2017.5.20欢(bei)乐(ju)赛解题报告

    预计分数:100+20+50=first 实际分数:20+0+10=gg 水灾(sliker.cpp/c/pas) 1000MS  64MB 大雨应经下了几天雨...

    attack
  • 算法细节系列(35):不一样的排序

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 不引入新的数组,实现数组元素交换位置函数

             最近遇到一道C++的面试题,要求不引入新的数组,实现数组元素交换位置函数,看似挺简单的,却还是花费了我不少时间,这里记录下来,给大家一个简单的...

    用户1221057
  • hdu 1598 find the most comfortable road(枚举+卡鲁斯卡尔最小生成树)

    find the most comfortable road Time Limit: 1000/1000 MS (Java/Others)    Memory ...

    Gxjun
  • BZOJ3143: [Hnoi2013]游走(期望DP 高斯消元)

    Description 一个无向连通图,顶点从1编号到N,边从1编号到M。  小Z在该图上进行随机游走,初始时小Z在1号顶点,每一步小Z以相等的概率随机选 择当...

    attack
  • 树上倍增法求LCA

    1.两结点的深度相同. 2.两结点深度不同. 第一步都要转化为情况1,这种可处理的情况。

    风骨散人Chiam
  • 1751:分解因数

    1751:分解因数 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述给出一个正整数a,要求分解成若干个正整数的乘积,即a = ...

    attack

扫码关注云+社区

领取腾讯云代金券