Distance to the nearest waypoint along a route

You are writing part of a car's navigation software. A route is a polyline: an ordered list of 2D waypoints coordinates, connected by straight segments from each waypoint to the next. The vehicle starts at coordinates[0] and drives along the route.

You are also given a list distances. Each value is the total distance driven since the start. For each value:

1. Find the vehicle's exact position on the route after driving that far (interpolate along the segment it is on).
2. Return the Euclidean distance from that position to the closest waypoint anywhere on the route, not only the two ends of the current segment.

Implement:

def nearest_checkpoint_distances(
    coordinates: list[tuple[float, float]],
    distances: list[float],
) -> list[float]: ...

Rules

• 1 <= len(coordinates) <= 10^5, 1 <= len(distances) <= 10^5. Coordinates are floats.
• distances is not necessarily sorted.
• A distance at or beyond the route's total length puts the vehicle on the last waypoint.
• A negative distance is invalid. Raise an error.
• Consecutive waypoints may be identical (zero-length segments).
• Answers are compared with a tolerance of 1e-6.

Example 1

coordinates = [(0, 0), (4, 0), (4, 3)]
distances   = [0, 1, 2, 5, 7, 100]
output      = [0, 1, 2, 1, 0, 0]

After 5 units you have driven the 4-unit first segment and 1 unit up the second, so you are at (4, 1), which is 1 away from (4, 0). 100 is past the end (length 7), so you are on (4, 3).

Example 2

coordinates = [(0, 0), (10, 0), (10, 1), (-10, 1)]
distances   = [21]
output      = [1]

After 21 units you are at (0, 1) on the last segment. Both ends of that segment are 10 away, but the first waypoint (0, 0) is only 1 away.

Aim for better than checking every waypoint for every query when both lists are large.

Reconstructed from the reported question; details may differ from what interviewers ask.