pku1151.cpp

POJ1151 Atlantis的源代码

///POJ1151 Atlantis 
///线段树 segment tree 求面积

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_ELem = 400;
const int MAX_Line = 200;
struct Node{
	short left, right;
	bool coverd;
	double len;
	//short segment;
	short count;
	bool leftcover, rightcover;
	struct Node *lcd, *rcd;
	void Build(int, int);
	void Update();
	void Insert(double, double);
	void Delete(double, double);
}SegTree[MAX_ELem];
struct Node *root = &SegTree[0];
struct Data{
	double x, y1, y2;
	bool left;
}line[MAX_Line];
double node_val[MAX_Line];
int up = 0;

void Node::Build(int l, int r)
{
	left = l;
	right = r;
	coverd = 0;
	len = 0;
	//segment = 0;
	count = 0;
	leftcover = rightcover = 0;
	if(r-l>1){
		int lenid = (l + r) / 2;
		lcd = &SegTree[++up];
		lcd->Build(l, lenid);
		rcd = &SegTree[++up];
		rcd->Build(lenid, r);
	}
}

void Node::Update()
{
	if(count>0){
		len = node_val[right] - node_val[left];
		//segment = 1;
		leftcover = rightcover = 1;
	}else if(right-left==1){
		len = 0;
		//segment= 0;
		leftcover = rightcover = 0;
	}else{
		len = lcd->len + rcd->len;
		//segment = lcd->segment + rcd->segment;
		//if(lcd->rightcover && rcd->leftcover)segment--;
		leftcover = lcd->leftcover;
		rightcover = rcd->rightcover;
	}
}

void Node::Insert(double l, double r)
{
	if(l<=node_val[left] && node_val[right]<=r){
		count++;
	}else{
		if(l<node_val[lcd->right]){
			lcd->Insert(l, r);
		}
		if(r>node_val[rcd->left]){
			rcd->Insert(l, r);
		}
	}
	Update();
}

void Node::Delete(double l, double r)
{
	if(l<=node_val[left] && node_val[right]<=r){
		count--;
	}else{
		if(l<node_val[lcd->right]){
			lcd->Delete(l, r);
		}
		if(r>node_val[rcd->left]){
			rcd->Delete(l, r);
		}
	}
	Update();
}

bool operator < (const Data &a, const Data &b)
{
	return a.x < b.x;
}

int main(int argc, char **argv) {
	//freopen("in","r",stdin);
	//freopen("out","w",stdout);
	int i, j, N, tstcs=1;
	double x1, y1, ans, x2, y2;
	while(scanf("%d",&N),N){
		i = 0;
		for(j=0;j<N;j++){
			scanf("%lf %lf %lf %lf",&x1, &y1, &x2, &y2);
			line[i].x = x1; line[i].y1 = y1; line[i].y2 = y2; line[i].left = 1; node_val[i++] = y1;
			line[i].x = x2; line[i].y1 = y1; line[i].y2 = y2; line[i].left = 0; node_val[i++] = y2;
		}
		N *= 2;
		sort(line, line+N);
		sort(node_val, node_val+N);
		j = 1;
		for(i=1;i<N;i++){
			if(node_val[i]!=node_val[i-1]){
				node_val[j++] = node_val[i];
			}
		}
		up = 0;
		ans = 0;
		//prev = 0;
		root->Build(0, j-1);
		for(i=0; i<N-1; i++){
			if(line[i].left){
				root->Insert(line[i].y1, line[i].y2);
			}else{
				root->Delete(line[i].y1, line[i].y2);
			}
			ans += (line[i+1].x - line[i].x)*root->len;
			//printf("ans = %lf\n",ans);
			//printf("segment = %d\n",root->segment);
			//printf("root->len = %lf\n",root->len);
			//printf("line[i+1].x = %lf\n",line[i+1].x);
			//printf("line[i].x = %lf\n\n",line[i].x);
			//ans += abs(root->len - prev);
			//prev = root->len;
		}
		//ans += root->len;
		printf("Test case #%d\n",tstcs++);
		printf("Total explored area: %.2lf\n\n",ans);
	}
	return 0;
}