个人感觉是不是算Y轴方向的边框时候可能有问题。。
#include <stdio.h>
#include <cassert>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

const int size = 20000;
const int rectangle_num = 5000;

//代表一条竖直边
typedef struct Vertical{
	int x;
	int up;
	int low;
	int flag;
}Vertical;

Vertical  verticals[rectangle_num * 2];

//Y轴坐标离散化
vector<int> hash_map;


typedef struct Node{
	int up;
	int low;
	int sc;//区间里有几段被覆盖
	int uf;//上顶点是否覆盖
	int lf;//下顶点是否覆盖
	int cover_len;//这个区间覆盖的长度
	int flag;//这个区间被覆盖几次
	Node *left_child;
	Node *right_child;

	void Insert(int, int, int);
	void Construct(int, int);
	void Update();
}Node;

int len=1;
Node sTree[size * 3];
Node *root = &sTree[0];

void Node::Construct(int l, int u)
{
	up = u;
	low = l;
	sc = 0;
	uf = 0;
	lf = 0;
	cover_len = 0;
	flag = 0;
	
	if( low+1 == up){
		left_child = right_child = NULL;
		return;
	}	

	int mid = ( up + low ) >> 1;
	left_child = &sTree[len++];
	right_child = &sTree[len++];

	left_child->Construct(low, mid);
	right_child->Construct(mid, up);
}

void Node::Insert(int l, int u, int f)
{
	if( low>=l && up<=u ){
		flag += f;
		return;
	}
		
	int mid = ( low + up ) >> 1;
	if( l < mid ){
		left_child->Insert(l, u, f);
	}
	if( u > mid){
		right_child->Insert(l, u, f);
	}
}

void Node::Update()
{
	if( flag > 0 ){
		lf = 1;
		uf = 1;
		cover_len = hash_map[up] - hash_map[low];
		sc = 1;	
		return;
	}
	if( low + 1 == up ){
		lf = 0;
		uf = 0;
		cover_len = 0;
		sc = 0;
		return;
	}		
	assert(left_child && right_child);
	left_child->Update();
	right_child->Update();
	
	lf = left_child->lf;
	uf = right_child->uf;
	cover_len = left_child->cover_len + right_child->cover_len;
	sc = left_child->sc + right_child->sc;
	if( left_child->uf==1 && right_child->lf==1){
		sc--;
	}		
}

bool compareVertical(Vertical one, Vertical two)
{
	return one.x < two.x;
}

int findIndex(int left, int right, int value)
{
	while( left <= right ){
		int mid = (left + right) >> 1;
		if(hash_map[mid] == value){
			return mid;
		}
		if( hash_map[mid] > value ){
			right = mid - 1;
		}else{
			left = mid + 1;
		}
	}

}


int main()
{
	int n;
	scanf("%d", &n);
	if( n == 0 ){
		printf("0\n");
		return 0;
	}	

	int index = 0;
	hash_map.clear();
	for(int i=1; i<=n; i++){
		int x1, y1, x2, y2;
		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
		Vertical elem;
		elem.x= x1;
		elem.low = y1;
		elem.up = y2;
		elem.flag = 1;
		verticals[index++] = elem;
		
		elem.x=x2;
		elem.flag = -1;
		verticals[index++] = elem;
		
		hash_map.push_back(y1);	
		hash_map.push_back(y2);	
	}
	
	sort(verticals, verticals+index, compareVertical);
	sort(hash_map.begin(), hash_map.end());
	vector<int>::iterator iter=unique(hash_map.begin(), hash_map.end());
	hash_map.erase(iter, hash_map.end());
	int hash_len = hash_map.size();
	len = 1;
	root->Construct(0, hash_len-1);
	
	int previous_x = verticals[0].x;
	int perimeter = 0;
	int last_sc = 0;
	int last_len = 0;
	root->Insert(findIndex(0, hash_len-1, verticals[0].low), findIndex(0, hash_len-1, verticals[0].up), verticals[0].flag);	
	for(int i=1; i<index; i++){
		if(verticals[i].x == verticals[i-1].x){
			root->Insert(findIndex(0, hash_len-1, verticals[i].low), findIndex(0, hash_len-1, verticals[i].up), verticals[i].flag);	
		}else{
			root->Update();
			perimeter += abs(root->cover_len-last_len); 
			perimeter += 2 * last_sc * (verticals[i-1].x-previous_x);
			last_sc = root->sc;
			last_len = root->cover_len;
			previous_x = verticals[i-1].x;		
		
			root->Insert(findIndex(0, hash_len-1, verticals[i].low), findIndex(0, hash_len-1, verticals[i].up), verticals[i].flag);	
		}
	}	
	root->Update();
	perimeter += abs(root->cover_len-last_len); 
	perimeter += 2 * last_sc * (verticals[index-1].x-previous_x);

	printf("%d\n", perimeter);	

	return 0;
}

• Orz (2) aixad 2009-11-13 01:02:36