809. The Moment They Come Close Enough
Two drones fly in straight lines at constant speed. At time 0 drone A is at (ax, ay) and
moves (avx, avy) metres per second; drone B is at (bx, by) and moves (bvx, bvy).
They can exchange data once they are within d metres of each other. Print the earliest time
t in the interval [0, T] at which the distance between them is at most d, to exactly 6
digits after the decimal point, or -1 if that never happens within T seconds.
A (0,0) moving (1,0), B (10,0) still, d = 1, T = 100 -> 9.000000
A (0,0) moving (1,0), B (10,5) moving (-1,0), d = 6, T = 100 -> 3.341688
A (0,0) still, B (10,0) still, d = 1, T = 100 -> -1
## Why the distance is not monotone, and what to do about it
Write dx = ax - bx, dy = ay - by for the starting offset and vx = avx - bvx,
vy = avy - bvy for the relative velocity. Then
distance(t)^2 = (dx + vx*t)^2 + (dy + vy*t)^2
which is a quadratic in t with a non-negative leading coefficient. Its graph is a valley: the
drones close in, reach their nearest point, and separate again. So the predicate "are they within
d at time t?" is FALSE, then true, then false again, and binary search applied to the whole
of [0, T] is meaningless.
The fix is the transferable idea of this problem. Cut the range at the bottom of the valley, where the distance IS monotone, and search only the left half:
t_close = -(dx*vx + dy*vy) / (vx*vx + vy*vy)
which is where the derivative of the quadratic is zero. On [0, t_close] the distance is
non-increasing, so within-d is false then true and the seam is the answer.
## The three cases to dispose of first
1. Already close enough at time 0: the answer is 0.000000, and no search is needed.
2. Zero relative velocity: the distance never changes, so if case 1 did not fire the answer is
-1. This is also the case that would divide by zero in the formula above.
3. t_close below 0, or beyond T after clamping, or a distance at t_close that is still
above d: they never get close enough inside the window, so -1.
Only what survives all three goes into the search.
## Working in squares
Never take a square root. Compare distance(t)^2 against d * d throughout: the comparison is
identical because both sides are non-negative, and it saves a hundred square roots as well as the
rounding each one carries.
## Why a closed form is not the point
The quadratic can of course be solved directly, and for this exact question that is a fine solution. What does not survive is the formula: make the drones follow curved paths, or add a third drone, and the algebra collapses while "find the valley floor, then search the monotone half" still works. That restriction to a monotone stretch is the idea worth taking away.
## The boundary that breaks a careless implementation
Clamping t_close to T before testing it. If the nearest approach happens after the window
closes, the correct question is whether they are close enough at T itself, not at the true
nearest point. The test with T = 5 and an answer that would have been 9 is exactly that case.
## Related problems
Problem 808 also manufactures a monotone quantity out of a valley-shaped one, by searching the slope instead of restricting the range.
## Cost
Time O(100). Space O(1).
Constraints - `-1000 ≤ ax, ay, bx, by ≤ 1000` - `-100 ≤ avx, avy, bvx, bvy ≤ 100` - `0 ≤ d ≤ 5000` - `1 ≤ T ≤ 10000` - every answer is at least `10^-9` away from a halfway rounding point at 6 digits
Input
One line containing ten integers: ax ay avx avy bx by bvx bvy d T.
Output
Print the earliest time in seconds at which the two drones are within d metres, with exactly 6 digits after the decimal point in plain fixed notation, or -1 on its own when no such time exists in [0, T]. Print nothing else on the line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.