Drone Charging Range
Medium · minimum bottleneck path
A delivery drone moves between charging stations. You are given stations, a list of points [x, y] with integer coordinates. The drone starts at the first station (index 0) and has to end at the last one.
The drone recharges fully at every station, and its battery allows it to fly one hop of any length up to a fixed range before it must land at another station. To avoid square roots, ranges are given as squared distances: a hop from [x1, y1] to [x2, y2] is possible when (x1 - x2)^2 + (y1 - y2)^2 <= R.
The drone may land at any stations along the way, in any order, and may use a station more than once.
Return the smallest integer R for which the drone can get from the first station to the last. If there is only one station, the drone is already there and the answer is 0.
Examples
Example 1
Input: stations = [[0, 0], [3, 4], [6, 8]]
Output: 25
Flying straight from the first station to the last needs R = 100. Landing at the middle station first makes both hops have squared length 25, so R = 25 is enough.
Example 2
Input: stations = [[0, 0], [5, 0]]
Output: 25
There is only one possible hop, with squared length 25.
Example 3
Input: stations = [[2, 2]]
Output: 0
The drone is already at the last station.
Constraints
- 1 <= len(stations) <= 300
- Each station is [x, y] with -10^4 <= x, y <= 10^4.
- Two stations may share the same coordinates.