Proficient.
Put your skills to the test.

Problem summary

A rescuer starts on a straight paved path parallel to the shore, separated from it by a sandy strip of width B. A swimmer starts A metres offshore and L metres from the rescuer, and swims perpendicularly toward shore at speed V. The rescuer’s maximum speeds on the path, sand and water are Va, Vp and Vw. Find their earliest meeting time.

Constraints

0 ≤ A,B ≤ 1000; 0 < A+B ≤ L ≤ 5000; 0 ≤ V < Vw ≤ 1.717; Vw ≤ Vp ≤ Va ≤ 6.132. Inputs have at most three decimal places. A meeting before the swimmer reaches shore is guaranteed.

Worked example

An independently prepared example for this explanation.

60 20 40
5 2.5 1 0

36.000

Solution analysis

1. The horizontal separation D is sqrt(L²−(A+B)²). For a proposed time t the swimmer’s depth is h = max(0,A−Vt). Find the shortest travel time to this fixed point. A fastest path has straight segments in each medium, with nonnegative horizontal distances x, y and z satisfying x+y+z=D. Its time is x/Va + sqrt(B²+y²)/Vp + sqrt(h²+z²)/Vw.
2. This is a convex minimization. At an interior minimum the marginal time cost per horizontal metre has a common value p. For a medium of width w and speed u this gives horizontal distance wpu/sqrt(1−(pu)²). The road caps p at 1/Va: if the sand and water cannot absorb D at this cap, the remaining distance is run on the road. Binary-search p below this cap; the horizontal distance in the two slower media increases monotonically.
3. Now binary-search the meeting time. The fixed-point travel time decreases as the swimmer approaches shore, whereas the allowed time increases, so feasibility is monotone. The bound L/Vw is sufficient because taking a straight path through the sand and water is no slower than traversing the initial straight-line distance entirely at Vw. In the first example D=0, so the route takes 40/2.5 + 20/1 = 36 seconds.

Why it works

Straightening any segment within a homogeneous medium cannot increase its time. Removing backwards horizontal motion and excursions into slower media yields the described layered path. Each segment cost is convex in its horizontal distance; equality of derivatives, with the road derivative as an upper cap, is therefore sufficient for a global minimum. The inner search implements these optimality conditions. A proposed time is feasible exactly when the minimum time to the swimmer’s position is at most it; this predicate is monotone. The outer search consequently converges to the first feasible time.

Watch out. L is the straight-line separation, not the horizontal distance. The swimmer keeps moving. Handle zero sand width and equal speeds without division by zero at the derivative cap.

An independently written complete program with standard headers.

#include<algorithm>
#include<cmath>
#include<iomanip>
#include<iostream>
using namespace std;
int main(){
    double length,sea,beach,roadSpeed,sandSpeed,waterSpeed,swimmerSpeed;
    cin>>length>>sea>>beach;
    cin>>roadSpeed>>sandSpeed>>waterSpeed>>swimmerSpeed;
    double horizontal=sqrt(max(0.0,length*length-(sea+beach)*(sea+beach)));
    auto travel=[&](double depth){
        double low=0;
        double high=1.0/roadSpeed;
        auto distance=[](double width,double speed,double slope){
            if(width==0){
                return 0.0;
            }
            double sine=slope*speed;
            return width*sine/sqrt(max(1e-30,1.0-sine*sine));
        };
        for(int iteration=0;iteration<100;++iteration){
            double middle=(low+high)/2;
            if(distance(beach,sandSpeed,middle)+distance(depth,waterSpeed,middle)<=horizontal){
                low=middle;
            }
            else{
                high=middle;
            }
        }
        // The lower endpoint never allocates more than the available distance.
        double sandDistance=distance(beach,sandSpeed,low);
        double waterDistance=distance(depth,waterSpeed,low);
        double roadDistance=max(0.0,horizontal-sandDistance-waterDistance);
        return roadDistance/roadSpeed+hypot(beach,sandDistance)/sandSpeed+
            hypot(depth,waterDistance)/waterSpeed;
    };
    double low=0;
    double high=length/waterSpeed;
    for(int iteration=0;iteration<100;++iteration){
        double middle=(low+high)/2;
        if(travel(max(0.0,sea-swimmerSpeed*middle))<=middle){
            high=middle;
        }
        else{
            low=middle;
        }
    }
    cout<<fixed<<setprecision(6)<<high<<'\n';
}