pku1389.cpp

PKU1389的源代码

/////POJ1389 Area of Simple Polygons 
//Segment tree 线段树 求面积
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_ELem = 5010;
const int MAX_Line = 2010;
struct Node{
	short left, right;
	bool coverd;
	int len;
	//short segment;
	short count;
	bool leftcover, rightcover;
	struct Node *lcd, *rcd;
	void Build(int, int);
	void Update();
	void Insert(int, int);
	void Delete(int, int);
}SegTree[MAX_ELem];
struct Node *root = &SegTree[0];
struct Data{
	int x, y1, y2;
	bool left;
}line[MAX_Line];
int 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;
		leftcover = lcd->leftcover;
		rightcover = rcd->rightcover;
	}
}

void Node::Insert(int l, int 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(int l, int 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;
	int x1, y1, ans, x2, y2;
	while(scanf("%d%d%d%d",&x1,&y1,&x2,&y2),x1!=-1){
		i = 0; j = 0;
		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;
		while(scanf("%d%d%d%d",&x1,&y1,&x2,&y2),x1!=-1){
		//	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 = i;
		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;
		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("%d\n",ans);
	}
	return 0;
}