Codeforces #330 Div1 B. Max and Bike

D落ちたけどBC結構速く解けたので、Unratedは残念。
http://codeforces.com/contest/594/problem/B

問題

半径Rの車輪の外周に計測器を付けた自転車でレースを行う。
自転車は一直線の道において速度Vで走る。
自転車はスタート地点より手前の任意の位置で走り出してよい。
計測器がスタート地点を経由した時点からゴール地点に到達するまでの時間を最小化する位置で走り出す場合、必要な時間を答えよ。

解法

移動距離をD、車輪が(A+B)周 (Aは整数、Bは1未満の小数)でゴールに到達するとする。
A=floor(D/(2πR))周分は計測器の位置と関係なく進む。
残りD-(2πRA)の距離を1周未満の回転で進むとき、できるだけ計測器が前に進むようにしたい。

車輪の中心から垂直上向きの半直線を考える。
スタート地点経由時はそこからB/2周反時計回り、ゴール地点到達時はB/2周時計回りの位置に来るようにすると車輪の中心に対する相対的な移動距離が最大となる。
その移動距離は2*sin(Bπ)となる。

この時中心は(2πR(A+B))移動するので、全体で2*(πR(A+B)+sin(Bπ))移動する。
二分探索でこの距離がD以上になる最小のBを求めれば、車輪の回転数がわかるので時間も求められる。

int N;
ll R,V;
ll S,F;
double M_PI;

double dist(double r,double lp) {
	double di=2*M_PI*r*lp;
	di += r*sin(M_PI*lp)*2;
	return di;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	M_PI=atan(1)*4;
	
	cin>>N>>R>>V;
	double round=2*M_PI*R;
	
	FOR(i,N) {
		cin>>S>>F;
		double D=F-S;
		double ret=floor(D/round);
		D=fmod(D,round);
		
		double LL=0,RR=1;
		FOR(j,100) {
			double MM=(LL+RR)/2;
			if(dist(R,MM)>=D) RR=MM;
			else LL=MM;
		}
		ret += LL;
		_P("%.12lf\n",ret*round/V);
	}
	
}

まとめ

結構珍しいタイプの幾何？
そのせいかSubmit数少なかった気がする。