1177 Picture

問題概要

座標平面上の、各辺が座標軸に平行なn個の長方形が与えられる。
これらの長方形の重なりの図形の周の長さを求めよ。

n≦5000,各座標の絶対値は1万以下である。

解法

グリッドをの配列を作って、長方形の内部を塗りつぶす。
このとき、あるグリッドのマスが長方形の内部で、その隣のマスが長方形の外部のときそこには境界があるはずなので周長を1カウントする。

考え方は上のままで、座標の値がやや大きいので座標圧縮する（必要ないかも？）。

ソースコード

int n,m,nx,ny,vx[10000],vy[10000];
int x1[5000],y1[5000],x2[5000],y2[5000];
bool a[10001][10001];

int main()
{
	scanf("%d",&n);
	rep(i,n)
	{
		scanf("%d%d%d%d",x1+i,y1+i,x2+i,y2+i);
		vx[2*i]=x1[i]; vx[2*i+1]=x2[i];
		vy[2*i]=y1[i]; vy[2*i+1]=y2[i];
	}
	vx[2*n]=vy[2*n]=10001; vx[2*n+1]=vy[2*n+1]=-10001;
	m=2*n+2;
	sort(vx,vx+m); nx=unique(vx,vx+m)-vx;
	sort(vy,vy+m); ny=unique(vy,vy+m)-vy;
	rep(i,n)
	{
		x1[i]=lower_bound(vx,vx+nx,x1[i])-vx; x2[i]=lower_bound(vx,vx+nx,x2[i])-vx;
		y1[i]=lower_bound(vy,vy+ny,y1[i])-vy; y2[i]=lower_bound(vy,vy+ny,y2[i])-vy;
	}
	
	rep(i,n)
	{
		for(int j=x1[i];j<x2[i];j++)for(int k=y1[i];k<y2[i];k++)a[j][k]=1;
	}
	int ans=0;
	for(int i=1;i<nx-1;i++)for(int j=1;j<ny-1;j++)
	{
		if(a[i][j]&&!a[i-1][j])ans+=vy[j+1]-vy[j];
		if(a[i][j]&&!a[i][j-1])ans+=vx[i+1]-vx[i];
		if(a[i][j]&&!a[i+1][j])ans+=vy[j+1]-vy[j];
		if(a[i][j]&&!a[i][j+1])ans+=vx[i+1]-vx[i];
	}
	printf("%d\n",ans);
	
	return 0;
}