Codeforces 198(#125 Div1) C. Delivering Carcinogen

問題

座標平面の原点が恒星。その周囲を円軌道で惑星が反時計回りに速度vpで周っていて、
惑星はt = 0のとき(xp, yp)にいる。
宇宙船が(x, y)にいて、宇宙船は好きな方向に速度vで動くことができる。

太陽から距離r以内に入ると熱くて死ぬ。宇宙船は最短で何秒で惑星に着けるか求めよ。

制約条件

入力は1万以下の非負整数
vp＜v

方針

宇宙船のほうが速いので、ある時間tで惑星に着けるなら、t≦t'な時間t'でも惑星に着ける（tで着いて後ろに密着してればいいので）
なので、tについて二分探索する。

ある時間tを決めたとき、惑星は円運動なので位置はすぐわかる。
その位置まで、宇宙船が最短距離で移動したとき、t以内の時間でいければよい。

円を迂回する二点の最短距離は、二点の線分に円がかぶらないときは単なる直線距離。
そうでない場合を考える。二点をA, B, 円をCとする。
AからCへ引いた接線の接点まで直線で行って、BからCへ引いた接線の接点まで円周上を行って、接点からは離れて直線でBまで行くのが最短。

円と接線はライブラリを用意しておくか、適当に方程式を解くか。

ソースコード

double xp, yp, vp, x, y, v, r;
P s, t, o(0, 0);
G g;

double calc(const P &p){
	
	if(distanceSP(L(s, p), o) + EPS > r) return abs(s - p);
	
	G h = tanCP(o, r, p);
	int c = ccw(s, p, o); if(c == 0) c = -1;
	int i, j;
	for(i = 0; i < g.size() && ccw(s, p, g[i]) == c; i++);
	for(j = 0; j < h.size() && ccw(s, p, h[j]) == c; j++);
	
	
	double a = arg(g[i]), b = arg(h[j]);
	if(a > b) b += 2 * PI;
	a = b - a;
	if(a > PI) a = 2 * PI - a;
	
	return r * a + abs(s - g[i]) + abs(p - h[j]);
}

int main(){
	cin >> xp >> yp >> vp >> x >> y >> v >> r;
	s = P(x, y);
	t = P(xp, yp);
	g = tanCP(o, r, s);
	
	double w = vp / abs(t);
	double lo = 0, hi = 1e8, mid;
	
	rep(it, 100){
		mid = (lo + hi) / 2;
		P p = t * P(cos(mid * w), sin(mid * w));
		if(calc(p) < mid * v) hi = mid;
		else lo = mid;
	}
	
	printf("%.20f\n", lo);
	return 0;
}