続いて4問目。
http://utpc2012.contest.atcoder.jp/tasks/utpc2012_04
ある図形と、それを縮小回転した図形が与えられるので、前後で移動してない点を求める。
図形はいくつも点があるけど、最初の2点があると、両図形の最初の図形および縮小回転の様子がわかる。
よって、「最初の点の座標 + V * (最初の2点の座標の差)」が両図形で一致するVおよびその座標を求めればよい。
これは結局2変数の連立方程式になるので逆行列を求めて解けばよい。
なお、周りの回答を見ると全く違う人たちがいて気になったけど、解説によると「同じ縮小回転を繰り返せばいずれ不動点に収束する」ようだ。
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; }
まとめ
最初の2点だけに注目して、一気に解けたのは良かった。
変換を繰り返して収束させるのは思いつかなかったな…。