UTPC2012 : D - 地図が２枚

続いて４問目。
http://utpc2012.contest.atcoder.jp/tasks/utpc2012_04

ある図形と、それを縮小回転した図形が与えられるので、前後で移動してない点を求める。

図形はいくつも点があるけど、最初の２点があると、両図形の最初の図形および縮小回転の様子がわかる。
よって、「最初の点の座標 + V * (最初の２点の座標の差)」が両図形で一致するVおよびその座標を求めればよい。
これは結局２変数の連立方程式になるので逆行列を求めて解けばよい。

なお、周りの回答を見ると全く違う人たちがいて気になったけど、解説によると「同じ縮小回転を繰り返せばいずれ不動点に収束する」ようだ。

int N;
double PX[2][30],PY[2][30];
double vecx[2],vecy[2];

void solve() {
	ll x,y,i,j,rr,TM;
	ll p,t,c;
	
	N=GETi();
	FOR(i,2) {
		FOR(j,N) {
			scanf("%lf",&PX[i][j]);
			scanf("%lf",&PY[i][j]);
		}
		vecx[i]=PX[i][1]-PX[i][0];
		vecy[i]=PY[i][1]-PY[i][0];
	}
	
	// TX = CX + VX*X-VY*Y
	// TY = CY + VY*X+VX*Y
	
	// AX+BY=C
	// DX+EY=F
	double A,B,C,D,E,F,X,Y,P;
	A=vecx[0]-vecx[1];
	B=-vecy[0]+vecy[1];
	C=PX[1][0]-PX[0][0];
	D=vecy[0]-vecy[1];
	E=vecx[0]-vecx[1];
	F=PY[1][0]-PY[0][0];
	
	P=1/(A*E-B*D);
	X = P * (E*C-B*F);
	Y = P * (-D*C+A*F);
	
	double TX = PX[0][0]+vecx[0]*X-vecy[0]*Y;
	double TY = PY[0][0]+vecy[0]*X+vecx[0]*Y;
	_P("%.7lf %.7lf\n",TX,TY);
	
	return;
}

まとめ

最初の２点だけに注目して、一気に解けたのは良かった。
変換を繰り返して収束させるのは思いつかなかったな…。