Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

线段树+扫描线,代码如下

Posted by 2007011268 at 2012-07-12 11:55:33 on Problem 1151
#include <iostream>
#include <cstdio>
#include <algorithm>
#define M 1000
using namespace std;
struct node
{
	int l,r;
	int cov;
	double len;
};
struct line
{
	double x;
	double y1;
	double y2;
	char f;
};
struct line_cmp
{
	bool operator()(const line& a, const line& b)
	{
		return a.x < b.x;
	}
};
class seg_tree
{
private:
	node tree[M];
	double number[M];  //the true value of the index l, r and mid
	size_t ncount;      //the number of nodes in the tree
public:
	seg_tree(const double * a, int len);
	void build(int l, int r, int root);
	void del(int l, int r, int p);
	void insert(int l, int r, int p);
	double get_len() { return tree[1].len; }
};
seg_tree::seg_tree(const double * a, int len)
{
	for(size_t i=0; i<len; i++)
		number[i] = a[i];
	ncount = len;
	build(0, len-1, 1);   //build the seg tree
}
void seg_tree::build(int l, int r, int root)
{
	tree[root].l = l;
	tree[root].r = r;
	tree[root].cov = 0;
	tree[root].len = 0;
	if(l + 1 == r)
		return;
	int mid = (l + r) >> 1;
	build(l, mid, 2*root);
	build(mid, r, 2*root+1);
}
void seg_tree::del(int l, int r, int p)
{
	if(tree[p].l == l && tree[p].r == r)
	{
		tree[p].cov --;
		if(tree[p].cov <= 0)
		{
			if(tree[p].l + 1 < tree[p].r)
				tree[p].len = tree[2*p].len + tree[2*p+1].len;
			else
				tree[p].len = 0;
		}
		return;
	}
	else
	{
		int mid = (tree[p].l + tree[p].r) >> 1;
		if( r <= mid)
			del(l, r, 2*p);
		else if(l >= mid)
			del(l, r, 2*p+1);
		else
		{
			del(l, mid, 2*p);
			del(mid, r, 2*p+1);
		}
		if(tree[p].cov == 0)
			tree[p].len = tree[2*p].len + tree[2*p+1].len;
	}
}
void seg_tree::insert(int l, int r, int p)
{
	if(tree[p].l == l && tree[p].r == r)
	{
		tree[p].cov ++;
		tree[p].len = number[r] - number[l];
		return;
	}
	else
	{
		int mid = (tree[p].l + tree[p].r) >> 1;
		if(r <= mid)
			insert(l, r, 2*p);
		else if(l >= mid)
			insert(l, r, 2*p+1);
		else
		{
			insert(l, mid, 2*p);
			insert(mid, r, 2*p+1);
		}
		if(tree[p].cov==0)
			tree[p].len = tree[2*p].len + tree[2*p+1].len;
	}
}
int main()
{
	int n;
	size_t test_count = 0;
	double x1, y1, x2, y2;
	double yval[M];
	line data[M];
	while(cin >> n && n != 0)
	{
		test_count ++;
		int l1 = 0;
		int l2 = 0;
		for(int i=0; i<n; i++)
		{
			cin >> x1 >> y1 >> x2 >> y2;
			yval[l1++] = y1;	
			yval[l1++] = y2;
			data[l2].x = x1;
			data[l2].y1 = y1;
			data[l2].y2 = y2;
			data[l2].f = -1;
			l2 ++;
			data[l2].x = x2;
			data[l2].y1 = y1;
			data[l2].y2 = y2;
			data[l2].f = 1;
			l2 ++;
		}
		sort(yval, yval+l1);
		sort(data, data+l2, line_cmp());
		l1 = unique(yval, yval+l1) - yval;
		double sum = 0;
		seg_tree stree(yval, l1);
		for(int i=0; i<l2-1; i++)
		{
			int l, r;
			l = lower_bound(yval, yval + l1, data[i].y1) - yval;
			r = lower_bound(yval, yval + l1, data[i].y2) - yval;
			if(data[i].f == -1)
				stree.insert(l, r, 1);
			else
				stree.del(l, r, 1);
			sum += stree.get_len() * (data[i+1].x - data[i].x);
		}
		printf("Test case #%d\n", test_count);
		printf("Total explored area: ");
		printf("%.2f", sum);
		printf("\n\n");
	}
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator