记录编号	156225	评测结果	AAAAA
题目名称	[IOI 1998] 矩形周长	最终得分	100
用户昵称	水中音	是否通过	通过
代码语言	C++	运行时间	0.012 s
提交时间	2015-04-03 15:43:56	内存使用	0.85 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,anum,bnum,cnum,i,p,k,ANS;
int ux,uy,vx,vy,lastans,lasth,L,R,bh0=0,bh1=1;

struct aedge{int h,l,r,z;}A[10010];
struct bedge{int h,l,r,z;}B[10010];

inline bool MINA(const aedge&a,const aedge&b){return a.h<b.h;}
inline bool MINB(const bedge&a,const bedge&b){return a.h<b.h;}
/*-----------------------------------------------------------*/
struct www{int l,r,z;}C[2][10010]; 
inline bool MI(const www&a,const www&b)
{	
	if(a.l!=b.l)return a.l<b.l;
	if(a.r!=b.r)return a.r<b.r;
	return a.z<b.z;
}
/*-----------------------------------------------------------*/
void init()
{
	int MAX=0,MIN=30000;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{//1插入，0删除 
		scanf("%d%d%d%d",&ux,&uy,&vx,&vy);

		A[++anum]=(aedge){ux,uy,vy,anum+1};
		A[++anum]=(aedge){vx,uy,vy,anum+1};
		B[++bnum]=(bedge){uy,ux,vx,bnum+1};
		B[++bnum]=(bedge){vy,ux,vx,bnum+1};
	}
	sort(A+1,A+(anum+1),MINA);
	sort(B+1,B+(bnum+1),MINB);
}
int main()
{
	freopen("picture.in","r",stdin);
	freopen("picture.out","w",stdout);
	init();i=1;lastans=0;
	while(i<=anum)
	{
		ANS+=lastans*(A[i].h-lasth);lasth=A[i].h;
		while(A[i].h==lasth)
		C[bh0][++cnum]=(www){A[i].l,A[i].r,A[i].z},i++;
		
		L=-1e9,R=-1e9;lastans=0;sort(C[bh0]+1,C[bh0]+(cnum+1),MI);
		for(k=0,p=1;p<=cnum;p++)
		{
			if(p<cnum&&C[bh0][p+1].z==(C[bh0][p].z^1)){p++;continue;}
			C[bh1][++k]=C[bh0][p];
			if(C[bh0][p].l<=R){if(R<C[bh0][p].r)R=C[bh0][p].r;}
			else lastans++,L=C[bh0][p].l,R=C[bh0][p].r;
		}
		cnum=k;bh0^=1,bh1^=1;
	}i=1;lastans=0;
	while(i<=bnum)
	{
		ANS+=lastans*(B[i].h-lasth);lasth=B[i].h;
		while(B[i].h==lasth)
		C[bh0][++cnum]=(www){B[i].l,B[i].r,B[i].z},i++;
		
		L=-1e9,R=-1e9;lastans=0;sort(C[bh0]+1,C[bh0]+(cnum+1),MI);
		for(k=0,p=1;p<=cnum;p++)
		{
			if(p<cnum&&C[bh0][p+1].z==(C[bh0][p].z^1)){p++;continue;}
			C[bh1][++k]=C[bh0][p];
			if(C[bh0][p].l<=R){if(R<C[bh0][p].r)R=C[bh0][p].r;}
			else lastans++,L=C[bh0][p].l,R=C[bh0][p].r;
		}
		cnum=k;bh0^=1,bh1^=1;
	}
	ANS<<=1;
	printf("%d\n",ANS);
	return 0;
}