会津合宿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; }