会津合宿2012 3日目 C問題 KND Runs for Sweets

方針

f(x, y)を、点(x, y)を中心にしたときの、移動距離の最大値とする。
これをxを決め打ちして、yについての関数と見れば三分探索で最小値が求まる。


なので、xについて三分探索をしてやれば全体での最小値が求まる。

ソースコード

int n, x[100], y[100], v[100];

inline double d(double x, double y){
	return sqrt(x * x + y * y);
}
inline double g(double a, double b){
	double res = 0;
	rep(i, n) res = max(res, d(a - x[i], b - y[i]) / v[i]);
	return res;
}
inline double f(double x){
	double l = 0, r = 100, a, b;
	rep(i, 100){
		a = (l * 2 + r) / 3;
		b = (l + r * 2) / 3;
		if(g(x, a) > g(x, b)) l = a;
		else r = b;
	}
	return g(x, l);
}

int main(){
	while(cin >> n, n){
		rep(i, n) cin >> x[i] >> y[i] >> v[i];
		
		double l = 0, r = 100, a, b;
		rep(i, 100){
			a = (l * 2 + r) / 3;
			b = (l + r * 2) / 3;
			if(f(a) > f(b)) l = a;
			else r = b;
		}
		printf("%.9f\n", f(l));
	}
	return 0;
}