A survey drone flies in a straight line at constant velocity: at time t it is at (x0 + vx * t, y0 + vy * t). On the ground are radio beacons at fixed points. The drone's link quality depends on the sum of its distances to all the beacons, so the mission planner wants to know how small that sum gets during the flight window 0 <= t <= T (time is continuous).
Write min_total_distance(start: tuple[float, float], velocity: tuple[float, float], beacons: list[tuple[float, float]], T: float) -> float that returns the smallest value of
D(t) = sum over beacons (bx, by) of sqrt((x0 + vx*t - bx)**2 + (y0 + vy*t - by)**2)
over t in [0, T], accurate to within 1e-6 (absolute or relative, whichever is looser).
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)
Constraints: 1 <= len(beacons) <= 2000, 0 < T <= 10^6, coordinates and velocity components between -10^4 and 10^4 (velocity may be (0, 0)). Sampling many time steps is both slow and inaccurate; there is no neat formula for the best t.
Show hint
each distance is a convex function of t (a point moving in a straight line gets closer, then farther), and a sum of convex functions is convex, so D has no false dips: ternary search on t (about 100 rounds), then return D at the final point.