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-08-11 20:34:23 on Problem 1177
1.此题数据没有考虑边重合现象
2.网上的大部分解法也没有考虑到边重合现象

因为,我修改了网上的解法,分衡量和纵向两次分别求出横向部分的周长以及纵向部分的周长,然后相加就得到结果。

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5010;
struct Line
{
	int start, end;
	int dim;
	bool in;
	bool operator<(const Line & a) const
	{
		return dim < a.dim;
	}
};
Line line[2*N];
int val[2*N];
int X[2*N];
int Y[2*N];
int n, val_size;

struct Node
{
	int left, right, len;
	int seg_num, cover_len;
	int cover;
	bool lcover, rcover;
	Node()
	{
		left = right = 0;
		len = seg_num = cover_len = cover = 0;
		lcover = rcover = false;
	}
};
class SegTree
{
private:
	int max_val;
	Node tree[8*N];
	void get_cover_len(int num);
	void get_seg_num(int num);
public:
	SegTree(int val = 0);
	void build(int l, int r, int num);
	void insert(int l, int r, int num);
	void del(int l, int r, int num);
	int get_cover_len()
	{
		return tree[1].cover_len;
	}
	int get_seg_num()
	{
		return tree[1].seg_num;
	}
};
SegTree::SegTree(int v)
{
	max_val = v;
	build(0, v-1, 1);
}
void SegTree::get_cover_len(int num)
{
	if(tree[num].cover > 0)
		tree[num].cover_len = tree[num].len;
	else if(tree[num].right - tree[num].left > 1)
		tree[num].cover_len = tree[2*num].cover_len + tree[2*num+1].cover_len;
	else
		tree[num].cover_len = 0;
}
void SegTree::get_seg_num(int num)
{
	if(tree[num].cover > 0)
	{
		tree[num].lcover = tree[num].rcover = true;
		tree[num].seg_num = 1;
	}
	else if(tree[num].right - tree[num].left > 1)
	{
		tree[num].lcover = tree[2*num].lcover;
		tree[num].rcover = tree[2*num+1].rcover;
		tree[num].seg_num = tree[2*num].seg_num + tree[2*num+1].seg_num - (tree[2*num].rcover * tree[2*num+1].lcover);
	}
	else
	{
		tree[num].lcover = tree[num].rcover = false;
		tree[num].seg_num = 0;
	}
}
void SegTree::build(int l, int r, int num)
{
	tree[num].left = l;
	tree[num].right = r;
	tree[num].len = val[r] - val[l];
	if(r - l > 1)
	{
		int mid = (l + r) >> 1;
		build(l, mid, 2*num);
		build(mid, r, 2*num+1);
	}
}
void SegTree::insert(int l, int r, int num)
{
	if(tree[num].left == l && tree[num].right == r)
	{
		tree[num].cover ++;
	}
	else
	{
		int mid = (tree[num].left + tree[num].right) >> 1;
		if(r <= mid)
			insert(l, r, 2*num);
		else if(l >= mid)
			insert(l, r, 2*num+1);
		else
		{
			insert(l, mid, 2*num);
			insert(mid, r, 2*num+1);
		}
	}
	get_cover_len(num);
	get_seg_num(num);
}
void SegTree::del(int l, int r, int num)
{
	if(tree[num].left + 1 == tree[num].right)
	{
		if(tree[num].cover > 0)
			tree[num].cover --;
	}
	else
	{
		if(tree[num].cover > 0)
		{
			tree[num].cover --;
			tree[2*num].cover ++;
			tree[2*num+1].cover ++;
		}
		int mid = (tree[num].left + tree[num].right) >> 1;
		if(r <= mid)
		{
			del(l, r, 2*num);
			get_cover_len(2*num+1);
			get_seg_num(2*num+1);
		}
		else if(l >= mid)
		{
			del(l, r, 2*num+1);
			get_cover_len(2*num);
			get_seg_num(2*num);
		}
		else
		{
			del(l, mid, 2*num);
			del(mid, r, 2*num+1);
		}
	}
	get_cover_len(num);
	get_seg_num(num);
}
int get_res()
{
	int total = 0;
	SegTree seg_tree(val_size);
	for(int i=0; i<2*n-1; i++)
	{
		int start = lower_bound(val, val+val_size, line[i].start) - val;
		int end = lower_bound(val, val+val_size, line[i].end) - val;
		if(line[i].in)
			seg_tree.insert(start, end, 1);
		else
			seg_tree.del(start, end, 1);
		total += seg_tree.get_seg_num() * (line[i+1].dim - line[i].dim) * 2;
	}
	return total;
}
int get_horizon_len()
{
	for(int i=0; i<n; i++)
	{
		line[2*i].start = Y[2*i];
		line[2*i].end = Y[2*i+1];
		line[2*i].dim = X[2*i];
		line[2*i].in = true;
		line[2*i+1].start = Y[2*i];
		line[2*i+1].end = Y[2*i+1];
		line[2*i+1].dim = X[2*i+1];
		line[2*i+1].in = false;

		val[2*i] = Y[2*i];
		val[2*i+1] = Y[2*i+1];
	}
	sort(line, line+2*n);
	sort(val, val+2*n);
	val_size = unique(val, val+2*n) - val;
	return get_res();
}
int get_verticle_len()
{
	for(int i=0; i<n; i++)
	{
		line[2*i].start = X[2*i];
		line[2*i].end = X[2*i+1];
		line[2*i].dim = Y[2*i];
		line[2*i].in = true;
		line[2*i+1].start = X[2*i];
		line[2*i+1].end = X[2*i+1];
		line[2*i+1].dim = Y[2*i+1];
		line[2*i+1].in = false;

		val[2*i] = X[2*i];
		val[2*i+1] = X[2*i+1];
	}
	sort(line, line+2*n);
	sort(val, val+2*n);
	val_size = unique(val, val+2*n) - val;
	return get_res();
}
int main()
{
	cin >> n;
	int x1, y1, x2, y2;
	for(int i=0; i<n; i++)
	{
		cin >> X[2*i] >> Y[2*i] >> X[2*i+1] >> Y[2*i+1];
	}
/*	cout << "Verticle:" << endl;
	cout << get_verticle_len() << endl;
	cout << "Hozrizontal:" << endl;
	cout << get_horizon_len() << endl;
*/
	cout << get_verticle_len() + get_horizon_len() << endl;
	return 0;
}

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