Editorial for Swim, Run, Solve
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Editorialist:
Swim, Run, Solve is the second question for the 5th PCS Standard Contest.
The most important thing to note from the given question is that for any given crossover point \(c\), our time to get to the computer is:
\(t = \dfrac{\sqrt{c^2 + y_w^2}}{v_w} + \dfrac{\sqrt{(x-c)^2 + y_s^2}}{v_s}\)
Using this information, and the fact that our time to completion will have a smallest time over the whole search space, we can easily implement a ternary search that estimates until we get to a good enough precision.
#include <bits/stdc++.h>
using namespace std;
#define ld long double
int T;
ld x, yw, ys, vw, vs;
const ld PREC = 1e-11;
ld time(ld c) {
return sqrt(c*c+yw*yw)/vw + sqrt((x-c)*(x-c)+ys*ys)/vs;
}
int main() {
cin >> T;
while (T--) {
cin >> x >> yw >> ys >> vw >> vs;
long double lo = 0, hi = x;
for (int i = 0; i < 30; ++i) {
long double mid = (lo+hi)/2;
if (time(mid) < time(mid+(hi-lo)*PREC)) hi = mid;
else lo = mid;
}
cout << fixed << setprecision(20) << time(lo) << endl;
}
}
Comments