1066-Legend of Storia

問題概要

日本語なので略

解法

回転の中心点から回転してみて最も早くぶつかるものを次の回転元の点にする．

実装(C++)

幾何はほぼSpagetthiSourceなので省略
atan(Point)はatan2(imag(a),real(a))

#include <complex>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <iomanip>
#include <cstring>
#include <queue>
#include <map>
#include <cassert>
#include <boost/format.hpp>
using namespace std;

const double EPS=1e-7;
const double INF=1e10;
const double PI=3.1415926535897932384626433827950;

/*幾何ライブラリ*/

Point rotate(const Point &a,double r){
	return Point(a.real()*cos(r)-sin(r)*a.imag(),sin(r)*a.real()+cos(r)*a.imag());
}

int N,Q;
double R;
Polygon P;

//円に接しているものを探索する
int search(){
	for(int i=0;i<(int)P.size();i++){
		if(abs(abs(P[i])-R)<EPS)return i;
	}
	cerr<<"見つからなかったのです"<<endl;
	exit(-1);
}
Polygon next(Polygon now,int &s){
	Polygon res(now);
	Circle main(0,0,R);
	double MR=3*PI;
	for(int i=0;i<N;i++){
		if(i==s)continue;//回転不能
		Circle c(now[s],abs(now[i]-now[s]));
		double tmp=atan(now[i]-now[s]);
		pair<Point,Point> p=crosspoint_CC(c,main);
		double a1=atan(p.first-now[s])-tmp;
		double a2=atan(p.second-now[s])-tmp;
		a1=fmod(a1+6*PI,2*PI);
		a2=fmod(a2+6*PI,2*PI);
		if(a1<EPS)a1=2*PI;
		if(a2<EPS)a2=2*PI;
		MR=min(MR,a1);
		MR=min(MR,a2);
	}
	for(int i=0;i<N;i++){
		if(i==s)continue;
		res[i]=rotate(now[i]-now[s],MR)+now[s];
	}
	int nex=-1;
	for(int i=0;i<N;i++){
		if(i==s)continue;
		if(abs(abs(res[i])-R)<EPS)nex=i;
	}
	s=nex;
	if(s==-1){
		cerr<<"見つからなかったのです"<<endl;
		exit(-1);
	}
	return res;
}
int main() {
	while(cin>>N>>R>>Q){
		if(N==0)break;
		P=Polygon(N);
		for(int i=0;i<N;i++){
			cin>>P[i].real()>>P[i].imag();
		}
		int x=search();
		for(int i=0;i<Q;i++){
			P=next(P,x);
			cout<<boost::format("%.12f %.12f")%P[x].real()%P[x].imag()<<endl;
		}
	}
	return 0;
}