progress

~/problems / Search tricks / Ternary search

When is the drone closest to the beacons?

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

easy ~15 min

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.

Topic: Ternary search. Maximize a unimodal function; or binary search on the slope.

0:00
Ctrl ' run · Ctrl ↵ submit
esc