poj1151 Atlantis

Description

Input

Output

Sample Input

2
10 10 20 20
15 15 25 25.5
0

Sample Output

Test case #1
Total explored area: 180.00 

Source

Mid-Central European Regional Contest 2000

以前线段树的写法十分没效率……写了个更屌的

#include<map>
#include<string>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
#include<bitset>
#include<climits>
#include<list>
#include<iomanip>
#include<stack>
#include<set>
using namespace std;
double hs[210];
struct Tree
{
	int l,r,num;
	double val;
}tree[200<<2];
void create(int l,int r,int k)
{
	tree[k].l=l;
	tree[k].r=r;
	tree[k].val=0;
	tree[k].num=0;
	if(l+1==r)
		return;
	int m=l+r>>1;
	create(l,m,k<<1);
	create(m,r,k<<1|1);
}
void update(int l,int r,int k,int flag)
{
	if(tree[k].l==l&&tree[k].r==r)
	{
		tree[k].num+=flag;
		if(tree[k].num==0)
			tree[k].val=l+1==r?0:tree[k<<1].val+tree[k<<1|1].val;
		else
			tree[k].val=hs[r]-hs[l];
		return;
	}
	int m=tree[k].l+tree[k].r>>1;
	if(r<=m)
		update(l,r,k<<1,flag);
	else if(l>=m)
		update(l,r,k<<1|1,flag);
	else
	{
		update(l,m,k<<1,flag);
		update(m,r,k<<1|1,flag);
	}
	if(tree[k].num==0)
		tree[k].val=tree[k<<1].val+tree[k<<1|1].val;
}
struct Seg
{
	int flag;
	double l,r,y;
	bool operator <(Seg one)const
	{
		return y<one.y;
	}
}seg[210];
int main()
{
	int n,cs=0;
	while(cin>>n&&n!=0)
	{
		vector<double>box;
		for(int i=0;i<n;i++)
		{
			double x1,y1,x2,y2;
			cin>>x1>>y1>>x2>>y2;
			seg[i<<1].l=seg[i<<1|1].l=x1;
			seg[i<<1].r=seg[i<<1|1].r=x2;
			seg[i<<1].y=y1;
			seg[i<<1|1].y=y2;
			seg[i<<1].flag=1;
			seg[i<<1|1].flag=-1;
			box.push_back(x1);
			box.push_back(x2);
		}
		sort(box.begin(),box.end());
		box.erase(unique(box.begin(),box.end()),box.end());
		for(int i=0;i<box.size();i++)
			hs[i+1]=box[i];
		n*=2;
		sort(seg,seg+n);
		double ans=0;
		create(1,box.size(),1);
		for(int i=0;i<n;i++)
		{
			int l=1+lower_bound(box.begin(),box.end(),seg[i].l)-box.begin();
			int r=1+lower_bound(box.begin(),box.end(),seg[i].r)-box.begin();
			if(i!=n-1)
			{
				update(l,r,1,seg[i].flag);
				ans+=tree[1].val*(seg[i+1].y-seg[i].y);
			}
		}
		printf("Test case #%d\n",++cs);
		printf("Total explored area: %.2f\n\n",ans);
	}
}

poj1151 Atlantis

原文：http://blog.csdn.net/stl112514/article/details/45790519