我正在尝试解决一个竞争性编程问题，该问题要求我找到与另一个点最接近的点。使用的度量是曼哈顿距离。
到目前为止我已经尝试过
低效且复杂的解决方案
这就是我到目前为止所做到的。两点之间的曼哈顿距离为:
|x1 - x2| + |y1 - y2|
给定距离r，距离该点最多r距离的点满足不等式
|x1 - x2| + |y1 - y2| <= r
这在平面上形成一个类似菱形的形状(旋转 45 度的正方形)
所以我所做的是将这些点旋转 45 度，这样图形就变成了正方形。我现在可以检查两个点是否最多相距 r 个单位，它们的 x 和 y 坐标是否最多相距 r 个单位。
max(|x1 - x2|, |y1 - y2|) <= r
为了有效地检查数据库中的任何点是否距给定点最多 r 个单位，我使用线段树来查找位于 x 之间的所有点的 y 值- r 和 x + r 并检查是否至少有一个 y 值在 y - r 和 y + r 范围内>
由于我的任务是找到最小的曼哈顿距离，因此我对 r 的可能值应用了二分搜索。
我的解决方案在 O(log3 n) 时间内解决每个查询。一个 log n 来自二分搜索，一个用于检查线段树，另一个用于验证 y 值是否在范围内。 这对于问题的约束来说太多了。我最多需要 O(log2 n) 查询处理时间。
有人可以推荐一种性能更好的数据结构吗？
最佳答案
听起来像是 k-d-tree 的工作
关于c++ - 给定一组点，找到与查询点曼哈顿距离最小的点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/27587868/