Which depot is closest
A last-mile sheet lists every depot as an x, y position on a grid. Pick the depot nearest a delivery point, Manhattan distance.
- Distance is |x1 - x2| + |y1 - y2|, in whole units.
- A tie is broken by whoever comes first in the list.
- With no depots at all return -1.
nearestDepot(depots: list<Point>, x: int, y: int) → int
C++ needs a compiler and Drill does not host one yet, so this page is the reference rather than an exercise: the problem, worked examples, and the solution in full. To type it out, the same problem runs in Python.
Where you start
int nearestDepot(std::vector<Point> depots, int x, int y) {
}Worked examples
| Call | Result |
|---|---|
nearestDepot(std::vector<Point>{Point{0, 0}, Point{10, 0}, Point{3, 4}}, 4, 4) | 2 |
nearestDepot(std::vector<Point>{Point{0, 0}, Point{2, 2}}, 1, 1) | 0 |
nearestDepot(std::vector<Point>{Point{9, 9}}, 0, 0) | 0 |
nearestDepot(std::vector<Point>{}, 0, 0) | -1 |
Hint
Track a best index while you walk the list.
Reference solution in C++
int nearestDepot(std::vector<Point> depots, int x, int y) {
int best = -1, bestDist = INT_MAX;
for (size_t i = 0; i < depots.size(); i++) {
const auto& p = depots[i];
int d = std::abs(p.x - x) + std::abs(p.y - y);
if (d < bestDist) { bestDist = d; best = (int) i; }
}
return best;
}