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.

Authors: Tommoa

Editorialist: Tommoa

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

There are no comments at the moment.