kmjp's blog

競技プログラミング参加記です

yukicoder : No.471 直列回転機

同じ★3でもこちらは簡単。
http://yukicoder.me/problems/no/471

問題

2次元座標上にM個の点があり、その座標が与えられる。
ここで、各頂点に対し、N回の処理を順次施した。
各処理では、各点をある頂点に対しR度(90度の倍数)回転させる。

各処理の回転の中心や回転角は明には与えられない。
代わりに、点の座標を指定すると、N回の処理後その点がどこに移動したかが取得できる。
上記処理を最大10回まで用いて、元のM個の点がどこに移動したかを答えよ。

解法

N回の各処理の組み合わせは、結局アフィン変換になる。
よって最終的な平行移動と回転角をそれぞれ求めてしまえばよい。

(0,0)がどこに移動するかを問い合わせれば、各点がどの程度平行移動したかがわかる。
(1,0)がどこに移動するかを問い合わせ、(0,0)の移動後の座標と比べれば、回転角がわかる。

int M;
ll X[505050],Y[505050];
ll NX[2],NY[2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>M;
	FOR(i,M) cin>>X[i]>>Y[i];
	cout<<"? 0 0"<<endl;
	cin>>NX[0]>>NY[0];
	cout<<"? 1 0"<<endl;
	cin>>NX[1]>>NY[1];
	
	cout<<"!"<<endl;
	if(NX[1]-NX[0]==1) {
		FOR(i,M) cout<<X[i]+NX[0]<<" "<<Y[i]+NY[0]<<endl;
	}
	else if(NX[1]-NX[0]==-1) {
		FOR(i,M) cout<<-X[i]+NX[0]<<" "<<-Y[i]+NY[0]<<endl;
	}
	else if(NY[1]-NY[0]==1) {
		FOR(i,M) cout<<-Y[i]+NX[0]<<" "<<X[i]+NY[0]<<endl;
	}
	else if(NY[1]-NY[0]==-1) {
		FOR(i,M) cout<<Y[i]+NX[0]<<" "<<-X[i]+NY[0]<<endl;
	}
	
	
}

まとめ

すんなりでした。