poj 1177 矩形周长并 线段树.txt

ACM资料大集合

//POJ 1177
/*
//#include <iostream>
#include <stdio.h>
//include <algorithm>
#include <math.h>
#include <stdlib.h>
#include <time.h>
//using namespace std;

#define NMAX 30000
#define MAX 99999999
typedef struct noid
{
	int low;
	int high;
	int len;//测度
	int line;//连续段数
	int cc;//覆盖的线段个数
	int lcover,rcover;//左右端点是否被覆盖
}noid;

typedef struct shuxian
{
	int tag;//矩形的左竖线还是右竖线
	int x;//横坐标
	int y1;//低位纵坐标
	int y2;//高位纵坐标
}shuxian;

noid tree[NMAX*3];
shuxian shuru[NMAX];
shuxian chuli[NMAX];
int lisan[NMAX*2];
int temp[NMAX*2];
int lsnum;//离散后的不重复的纵坐标个数

void print_tree_lh()
{
	int i;
	printf("this is tree's low and high\n");
	for(i=1;i<=lsnum*3;i++)
	{
		printf("[%d %d]",tree[i].low,tree[i].high);
		if(i==1||i==3||i==7||i==15||i==31) printf("\n");
	}
	system("pause");
}

void print_tree_llc()
{
	int i;
	printf("this is tree's len, line and cc\n");
	for(i=1;i<=lsnum*3;i++)
	{
		printf("[%d %d %d %d %d]",tree[i].len,tree[i].line,tree[i].cc,tree[i].lcover,tree[i].rcover);
		if(i==1||i==3||i==7||i==15||i==31) printf("\n");
	}
	system("pause");
}
int cmpint(const void *a,const void *b)
{
	return (*(int *)a)-(*(int *)b);
}

int search_y(int key)
{
	int *p;
	p=(int *)bsearch(&key,lisan+1,lsnum,sizeof(int),cmpint);
	return p-lisan;
}

int cmppos(const void * a,const void * b)
{
	int tt=(((struct shuxian *)a)->x)-(((struct shuxian *)b)->x);
	if(tt==0) return (((struct shuxian *)a)->tag)-(((struct shuxian *)b)->tag);
	return tt;
}

void create(int p,int l,int h)
{
	int mid;
	mid=(l+h)/2;
	tree[p].low=l;
	tree[p].high=h;
	tree[p].len=tree[p].line=tree[p].cc=0;
	if(h-l>1)
	{
		create(p*2,l,mid);
		create(p*2+1,mid,h);
	}
}

void update(int p)
{
	if(p>=8000) printf("no\n");
//	printf("update (1) p=%d low=%d high=%d\n",p,tree[p].low,tree[p].high);
	if(tree[p].cc > 0) 
	{
		tree[p].lcover=tree[p].rcover=tree[p].line=1;
		tree[p].len=lisan[tree[p].high]-lisan[tree[p].low];
//		printf("update (2) tree[%d].len=%d\n",p,tree[p].len);
//		print_tree_llc();
	}
	else
	{
		if(tree[p].low+1 != tree[p].high)
		{
			tree[p].lcover=tree[2*p].lcover;
			tree[p].rcover=tree[2*p+1].rcover;
			tree[p].len=tree[2*p].len + tree[2*p+1].len;
			tree[p].line=tree[2*p].line + tree[2*p+1].line - tree[2*p].rcover * tree[2*p+1].lcover;
//			print_tree_llc();
		}
		else
		{
			tree[p].len=tree[p].lcover=tree[p].rcover=tree[p].line=0;
//			print_tree_llc();
		}
	}
}
void insert(int p,int l,int h)
{
	int mid;
	if(p>=8000) printf("no\n");
//	printf("insert p=%d l=%d h=%d\n",p,l,h);
	mid=(tree[p].low+tree[p].high)/2;
	if(l<=tree[p].low && h>=tree[p].high) tree[p].cc++;
	else
	{
		if(l<mid) insert(2*p,l,h);
	   	if(h>mid) insert(2*p+1,l,h); 	
	}
	update(p);
}
 
void ddelete(int p,int l,int h)
{
	int mid;
	if(p>=8000) printf("no\n");
	mid=(tree[p].low+tree[p].high)/2;
	if(l<=tree[p].low && h>=tree[p].high) tree[p].cc--;
	else
	{
		if(l<mid) ddelete(2*p,l,h);
	   	if(h>mid) ddelete(2*p+1,l,h); 	
	}
	update(p);
}

void init(int num)
{
	int i,j;
	for(i=1;i<=num;i++)
	{
//		printf("init (1) shuru[%d]=%d\n",i,shuru[i].x);
	}
	for(i=1;i<=num;i++) chuli[i]=shuru[i];
	for(i=1;i<=num;i++)
		qsort(chuli+1,num,sizeof(shuxian),cmppos);
	for(i=1;i<=num;i++)
	{
//		printf("init (2) chuli[%d]=%d\n",i,chuli[i].x);
	}
	for(i=1,j=0;i<=num;i++)
	{
		temp[++j]=chuli[i].y1;
		temp[++j]=chuli[i].y2;
	}
	qsort(temp+1,num*2,sizeof(int),cmpint);
	lisan[1]=temp[1];
	for(i=2,j=1;i<=2*num;i++)
	{
		if(temp[i]!=temp[i-1]) lisan[++j]=temp[i];
	}
	lsnum=j;
	for(i=1;i<=lsnum;i++)
	{
//		printf("init (3) lisan[%d]=%d\n",i,lisan[i]);
	}
	for(i=1;i<=lsnum;i++)
	{
//		printf("init (4) %d == %d\n",lisan[i],search_y(lisan[i]));
	}
	create(1,1,j);
//	print_tree_lh();
//	system("pause");
}

int solve(int num)
{
	int i,lastx,lasty,ans=0,be,end,qq;
	be=search_y(chuli[1].y1);
	end=search_y(chuli[1].y2);
//	printf("solve (1)\n"); 
	insert(1,be,end);
	lastx=chuli[1].x;
	lasty=tree[1].len;
	ans+=tree[1].len;
//	printf("ans=%d\n",ans);
//	print_tree_llc();
	for(i=2;i<=num;i++)
	{
		be=search_y(chuli[i].y1);
		end=search_y(chuli[i].y2);
		qq=2*tree[1].line*(chuli[i].x-chuli[i-1].x);
		ans+=qq;
		if(chuli[i].tag==1) insert(1,be,end);
		else ddelete(1,be,end);
//		printf("this is %d's line\n",i);
//		print_tree_llc();
		ans+=abs(tree[1].len-lasty);
//		printf("solve (2) henxian=%d shuxian=%d ans=%d\n",qq,abs(tree[1].len-lasty),ans);
//		system("pause");
		lastx=chuli[i].x;
		lasty=tree[1].len;
		
	}
	return ans;
}
int main()
{
	int num,i,ax,ay,bx,by;
	scanf("%d",&num);
	for(i=1;i<=num;i++)
	{
		scanf("%d%d%d%d",&ax,&ay,&bx,&by);

		shuru[2*i-1].tag=1;//左边
		shuru[2*i-1].x=ax;
		shuru[2*i-1].y1=ay;
		shuru[2*i-1].y2=by;

		shuru[2*i].tag=-1;
		shuru[2*i].x=bx;
		shuru[2*i].y1=ay;
		shuru[2*i].y2=by;
	}
	init(2*num);
	printf("%d\n",solve(2*num));
	scanf("%d %d",&num,&num);
	return 0;
}
*/

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#define MAX 10000

struct node
{
	int be,end,pos,tag;
}rect[MAX+1];

int line[2*MAX],len[2*MAX];
int b[2*MAX],e[2*MAX];
int cnt[2*MAX];
int lchild[2*MAX],rchild[2*MAX];
int lcover[2*MAX],rcover[2*MAX];
int tmp[MAX+1],aux[MAX+1];
int all,num,n;

int cmpint(const void *m,const void *n)
{
	return *((int *)m) - *((int *)n);
}

int cmprect(const void *m,const void *n)
{
	return ((struct node*)m)->pos - ((struct node *)n)->pos;
}

int search(int key)
{
	int *p;
	p=(int *)bsearch(&key,tmp+1,num,sizeof(int),cmpint);
	return p-tmp;
}

void build(int be,int end)
{
	int x=++all;
	b[x]=be;
	e[x]=end;
	cnt[x]=0;
	len[x]=0;
	line[x]=0;
	lcover[x]=rcover[x]=0;

	if(end-be>1) 
	{
		lchild[x]=all+1;
		build(be,(be+end)/2);
		rchild[x]=all+1;
		build((be+end)/2,end);
	}
}

void update(int root,int be,int end)
{
	if(cnt[root]>0)
	{
		len[root]=tmp[end]-tmp[be];
		lcover[root]=rcover[root]=1;
		line[root]=1;
	}
	else if(end-be>1)
	{
		len[root]=len[lchild[root]] + len[rchild[root]];
		lcover[root] = lcover[lchild[root]];
		rcover[root] = rcover[rchild[root]];
		line[root] = line[lchild[root]] + line[rchild[root]] - rcover[lchild[root]] * lcover[rchild[root]];
	}
	else
	{
		len[root]=line[root]=lcover[root]=rcover[root]=0;
	}
}

void insert(int root,int be,int end)
{
	if(be<=b[root] && end>=e[root]) cnt[root]++;
	else
	{
		if(be<(b[root]+e[root])/2) insert(lchild[root],be,end);
		if(end>(b[root]+e[root])/2) insert(rchild[root],be,end);
	}
	update(root,b[root],e[root]);
}

void del(int root,int be,int end)
{
	if(be<=b[root] && end>=e[root]) cnt[root]--;
	else
	{
		if(be<(b[root]+e[root])/2) del(lchild[root],be,end);
		if(end>(b[root]+e[root])/2) del(rchild[root],be,end);
	}
	update(root,b[root],e[root]);
}

void input()
{
	int i;
	int x1,y1,x2,y2;

	scanf("%d",&n);
	for(i=1;i<=2*n;i++)
	{
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		rect[i].be=y1;
		rect[i].end=y2;
		rect[i].tag=1;
		rect[i].pos=x1;
		aux[i]=y1;
		i++;
		rect[i].be=y1;
		rect[i].end=y2;
		rect[i].tag=0;
		rect[i].pos=x2;
		aux[i]=y2;
	}
}

void discrete()
{
	int i;
	qsort(rect+1,2*n,sizeof(struct node),cmprect);
	qsort(aux+1,2*n,sizeof(int),cmpint);

	num=1;
	tmp[1]=aux[1];
	for(i=2;i<=2*n;i++)
	{
		while(i<=2*n && aux[i]==aux[i-1]) i++;
		tmp[++num]=aux[i];
	}
}

int solve()
{
	int sum,last,i,left,right;

	all=0;
	build(1,num);

	sum=0; last=0;
	for(i=1; i<=2*n-1; i++)
	{
		left= search(rect[i].be);
		right= search(rect[i].end);

		if(rect[i].tag) insert(1,left,right);
		else del(1,left,right);

		sum+=2*(rect[i+1].pos-rect[i].pos)*line[1];
		sum+=abs(len[1]-last);
		last=len[1];
	}
	left=search(rect[i].be);
	right=search(rect[i].end);
	del(1,left,right);
	sum+=abs(len[1]-last);

	return sum;
}

int main()
{
	input();
	discrete();
	printf("%d\n",solve());
	scanf("%d",&n);
	return 0;
}