Straight Shot

This problem gives us a robot trying to get from 0,0 to X,0 with 2 caveats:

1. The robot contributes some constant amount to his ultimate velocity vector
2. There are ranges from some a<x<b such that the robot has some y component added to his velocity while he is traversing them

The problem asks for the time to reach the destination (so indirectly, the constant velocity vector the robot contributes).

We find we cannot calculate directly since the solution of initial theta will be transcendental. The general way around this is to binary search theta. This involves a problem since counterintuitively, aiming yourself more up could result in ending up further DOWN....aka...the function is not monotonic. Consider a single conveyor that goes down very fast. If we walk straight across it, we end up at some negative Y. If we aim further up, we spend MORE time on the super fast conveyor, so end up further down, despite our direction.

So lets do some math. We can see that the robot's position can be calculated piecewise:

• For each segment a<x<b and initial position a,y
• y' = y + (b-a)/Vcos(θ) * (V1+Vsin(θ))

This means for an initial velocity of V in direction θ, and segments of a,b,c with velocity V1 the final y position is:

(b-a)*V1/Vcosθ + (b-a)Vsinθ/Vcosθ
.................(b-a)tanθ
reduce LHS to constant and RHS apply distributive law
constant/cosθ + (b-a+c-b+d-c)tanθ
................(d-a)tanθ
K/cosθ+Xtanθ

This function is not monotonic, which we see when we take the derivative:

Ksin(θ)/cos^2(θ)+X(1+tan^2(θ))

Fortunately, we can reason a bit about it.

1. the RHS is always positive
2. the denominator of the LFS is always positive
3. the numerator of the LFS only switches signs at 0

Therefore, the function is monotonic if the range is either -pi/2<θ<0 OR 0<θ<pi/2.

Intuitively, if the conveyor belts carry us downward, we will have to angle upward, and vice versa. That restricts our range to either positive or negative theta, at which point we are guaranteed monotonic and can binary search. The initial case provided with the very fast belt would yield no solution.

Algorithm:

1. simulate with θ=0 to determine which direction the conveyors will carry you
2. evaluate the far endpoint of the correct quadrant based on outcome of (1) is not on the opposite side of y=0, there is no solution (the example with the fast belt will have this property)
3. binary search the quadrant for the intersection point