Codeforces Round #125 (Div. 1) C : Delivering Carcinogen

問題概要

原点のまわりを衛星が角速度Vp/rで等速円運動している。ロケットと衛星の初期位置が与えられる。ロケットは速度V(>Vp)で移動できる。原点から半径R以内に入らないようにして衛星までたどり着くには最小どれだけの時間が必要か求める問題。

解法

V>Vpなので二分探索できる。時間を決め打ちすれば衛星の位置が定まり、後は円を迂回するように線分の距離を求めるだけの問題に帰着される。

acceptされたコード

Point D, P, S;
real Vp, V, R;


void init() {
	real x, y;
	D = Point(0, 0);
	scanf("%lf %lf %lf", &x, &y, &Vp);
	P = Point(x, y);
	scanf("%lf %lf %lf %lf", &x, &y, &V, &R);
	S = Point(x, y);
}

Point get_target(real time){
	real dist = abs(P);
	real angle = arg(P);
	return Point(dist * cos((Vp / dist) * time + angle), dist * sin((Vp / dist) * time + angle));
}

real myabs(real x) {
	return x > 0 ? x : -x;
}

real diff(real x, real y) {
	real d = myabs(x - y);
	for(;d <= 2*PI;) d += 2*PI;
	for(;d>2*PI;) d -= 2*PI;
	return min(2*PI-d, d);
}

bool check(real time) {
	Point tar = get_target(time);
	real cd = distance_segment_point(S, tar, D);
	if (cd >= R) {
		return abs(S - tar) <= time * V;
	}

	real d = 0.0;
	pair<Point, Point> SC = tanCP(D, R, S), TC = tanCP(D, R, tar);
	d += get_dist(S, SC.first) + get_dist(tar, TC.first); //(S - SC.first) + abs(tar - TC.first);
	real mini = 1e9;
	mini = min(mini, diff(arg(SC.first), arg(TC.second)));
	mini = min(mini, diff(arg(SC.second), arg(TC.first)));
	d += R * mini;

	return d <= time * V;
}

real solve() {
	real low = 0.0, high = 1e9;

	for (int _ = 0; _ < 100; ++_) {
		real mid = (high + low) * 0.5;
		if (check(mid)) {
			high = mid;
		}
		else {
			low = mid;
		}
	}

	return low;
}

int main() {
	init();
	printf("%.13f\n", solve());

	return 0;
}