给定一个边为N的正方形网格。还给定网格上的一组输入点。需要在网格上找到与给定输入点具有最大曼哈顿距离的另一组点(可以是多个(。
例如，对于N = 4和输入[p1:{0, 0}, p2:{3, 3}]，输出应该是距离等于3的[{0, 3}, {1, 2}, {2, 1}, {3, 0}]。
0 1 2 3
┌───┬───┬───┬───┐
0 │p1 │ │ │ x │
├───┼───┼───┼───┤
1 │ │ │ x │ │
├───┼───┼───┼───┤
2 │ │ x │ │ │
├───┼───┼───┼───┤
3 │ x │ │ │p2 │
└───┴───┴───┴───┘
我的第一次尝试是一个简单的蛮力迭代——对于网格中的每个点，计算到每个输入点的曼哈顿距离，取最小值，最后从这些最小值中取最大值。这当然有效，但在大N和输入时速度较慢。
在我的第二次尝试中，我首先构建了一个kd树。Next迭代与之前几乎相同，不同之处在于现在我不计算每个输入点到的距离，而是计算到最近的一个(或多个(输入点的距离。这有点帮助，但还是有人告诉我有更好的算法。
您应该使用广度优先搜索，从所有给定点开始，同时查找每个单元格与其最近点的距离。这需要线性时间，而且很容易编码。
然后找到最高距离(或者记住它，因为它将是你写的最后一个(，并返回具有该距离的所有单元格。
如果你的分数不太稀疏，这将非常有效。如果它们相距很远，那么你需要一个算法，它会随着点的数量而不是网格的大小而增长。这将基于曼哈顿距离Voronoi图的计算，因为你想返回的所有点都在上面