A survey drone flies straight at constant velocity: at time t it is at (x0 + vx * t, y0 + vy * t). Its link quality depends on the sum of its distances to fixed ground beacons. How small does that sum get during 0 <= t <= T (continuous time)?
Write min_total_distance(start, velocity, beacons, T) -> float returning the minimum over t in [0, T] of
D(t) = sum over beacons (bx, by) of sqrt((x0 + vx*t - bx)**2 + (y0 + vy*t - by)**2)
within 1e-6 (absolute or relative).
min_total_distance((0, 0), (1, 0), [(5, 3)], 10) # 3.0 at t = 5 the drone is right under it
min_total_distance((0, 0), (1, 0), [(5, 3)], 2) # 4.2426... the window ends before t = 5; best is t = 2
min_total_distance((0, 0), (1, 1), [(0, 4), (4, 0)], 100) # 5.6568... (4 * sqrt(2) at t = 2)
Up to 2000 beacons; 0 < T <= 10^6; coordinates and velocity within ±10^4 (velocity may be (0, 0)). Sampling time steps is inaccurate, and there's no neat formula.
⭐ Bonus: a speed test with 2,000 beacons and T = 10^6 earns a star if you evaluate D only a few hundred times.
Show hint
each distance is convex in t, so their sum is too: ternary search on t (about 100 rounds) and return D at the final point.