2010 ICPC国内予選 A.角角画伯，かく悩みき

まさかの参加記より先に解説記事。参加記が永久に書かれない気がしてきた。

問題概要

正方形を座標平面状に、軸に平行に、かつ新しく並べる正方形は、既に並べた正方形のどれかと一辺がちょうど重なるように並べる。

2番目の正方形から、「（それまでに並べた正方形の中で）それが接する正方形の番号」、および「上下左右どの向きに接するか」が与えられたとき、全ての正方形を囲う座標軸に平行な長方形の幅と高さを求めよ。

解法

平行移動の自由度を除いて各正方形の位置は一意に定まる（しゃれじゃないよ！）ので、最初の正方形の（左上の点の）座標を(0,0)などと置いて、座標を全て求める。

y座標の最大値+1-y座標の最小値が高さ、x座標の最大値+1-x座標の最小値が幅になる。

ソースコード

int n,px[200],py[200];

int main(){
	while(cin>>n,n)
	{
		px[0]=py[0]=0;
		
		int x=0,X=0,y=0,Y=0;
		
		rep(i,n-1)
		{
			int m,d; cin>>m>>d;
			px[i+1]=px[m]+dx[d];
			py[i+1]=py[m]+dy[d];
			x=min(x,px[i+1]); X=max(X,px[i+1]);
			y=min(y,py[i+1]); Y=max(Y,py[i+1]);
		}
		cout<<X-x+1<<" "<<Y-y+1<<endl;
	}
	return 0;
}