学步园

此处的讲解更加详细与系统，代码也要好看100倍。

/*
 * poj1151 AC
 * 线段树+线段扫描+矩形分割
 * 计算平面上重叠矩形的总面积的经典问题
 *
 * 代码又长又丑，完全不能忍了。
 *
 * 实数坐标需要离散化，并且需要一个简单的hash数组对应
 * 分割方式有两种，纵向与横向，此处采用纵向分割。
 * 构造线段树时，注意其区间此处取[l,r)更为方便合适。
 * 初始化结构数组时，用构造函数。
 *
 * */
#include<cstdio>
#include<algorithm>
using namespace std;

struct NODE 
{
	double x1,x2,y;
	bool up;
}yy[1000];
int tot;
struct M
{
	double x;
	int num;
	bool fir;
}xx[1000];
int tot1;
double hash[2000];

bool cmpxx(const M &t1,const M &t2)
{
	return t1.x<t2.x;
}
bool cmpyy(const NODE &t1,const NODE &t2)
{
	return t1.y<t2.y;
}

inline void add(double x1,double x2,double y,int num,int up)
{
	yy[++tot].x1 = x1,yy[tot].x2 = x2;
	yy[tot].y = y,yy[tot].up = up;
	xx[++tot1].x = x1,xx[tot1].num = tot,xx[tot1].fir = true;
	xx[++tot1].x = x2,xx[tot1].num = tot,xx[tot1].fir = false;
	return;
}
struct TREE
{
	double y;
	int top,down;
	bool up;
}tree[5000];
bool mark[5000];

void pushdown(int x)
{
	tree[x<<1].y = tree[x<<1|1].y = tree[x].y;
	tree[x<<1].up = tree[x<<1|1].up = tree[x].up;
	mark[x<<1] = mark[x<<1|1] = true;
	tree[x<<1].top = tree[x].top,tree[x<<1].down = tree[x].down;
	tree[x<<1|1].top = tree[x].top,tree[x<<1|1].down = tree[x].down;
	mark[x] = false;
}

void build(int l,int r,int x)
{
	mark[x] = true,tree[x].y = 0,tree[x].up = true;
	tree[x].top = 0,tree[x].down = 0;
	if(l==r-1) return;
	int mid = (l+r)>>1;
	build(l,mid,x<<1);
	build(mid,r,x<<1|1);
}
	
double update(int t,int l,int r,int x)
{
	if(l>yy[t].x2 || r-1<yy[t].x1) return 0;
	if(yy[t].x1<=l && r-1<=yy[t].x2)
	{
		if(mark[x])
		{
			double s = (hash[r]-hash[l])*(yy[t].y-tree[x].y);
			if(tree[x].up && !yy[t].up && tree[x].down<=tree[x].top) s = 0;
			tree[x].y = yy[t].y,tree[x].up = yy[t].up;
			if(tree[x].up) tree[x].top++;
			else tree[x].down++;
			return s;
		}else
		{
			tree[x].y = yy[t].y;
			tree[x].up = yy[t].up;
		}
	}
	int mid = (l+r)>>1;
	if(mark[x]) pushdown(x);
	double s = update(t,l,mid,x<<1)+update(t,mid,r,x<<1|1);
	return s;
}

int main()
{
	int n,num = 0;
//	FILE *fin = fopen("d.in","r");
	while(true)
	{
		num++;
//		fscanf(fin,"%d",&n);
		scanf("%d",&n);
		if(!n) break;
		int i,sum = 0;
		double x1,x2,y1,y2;
		tot = tot1 = 0;
		for(i=1;i<=n;i++)
		{
//			fscanf(fin,"%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
			scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
			add(x1,x2,y1,i,false);
			add(x1,x2,y2,i,true);
		}

		sort(xx+1,xx+tot1+1,cmpxx);
		xx[0].x = -1;
		for(i=1;i<=tot1;i++)
		{
			if(xx[i].x>xx[i-1].x) sum++;
			hash[sum] = xx[i].x;
			if(xx[i].fir) yy[xx[i].num].x1 = sum;
			else yy[xx[i].num].x2 = sum-1;
		}

		sort(yy+1,yy+tot+1,cmpyy);
		double ans = 0;
		build(1,sum,1);
		for(i=1;i<=tot;i++)
			ans += update(i,1,sum,1);
		printf("Test case #%d\n",num);
		printf("Total explored area: %.2f\n\n",ans);
	}
	return 0;
}