这里的问题是找到所有整数点的集合，它给出从给定点集合的所有曼哈顿距离的最小总和！
例如：
让我们有一组给定的点 { P1, P2, P3...Pn }
基本问题是找到一个点，比如说 X，它在从点 { P1，P2，P3...Pn} 的所有距离上具有最小总和。
即|P1-X| + |P2-X| + .... + |Pn-X| = D，其中 D 将是所有 X 中的最小值。
更进一步，可以有多个 X 值满足上述条件。即，可能有多个 X 会给出相同的值 D。所以，我们需要找到所有这样的 X。
任何人都可以想到的一种基本方法是找到输入的中位数，然后暴力破解本文中提到的坐标
但是这种方法的问题是：如果中位数给出了两个相差很大的值，那么我们最终会暴力破解所有在给定时间内永远不会运行的点。
那么，即使这些点相距很远（其中中位数给出的范围约为 10 ^ 9），是否还有其他方法可以给出结果。
您可以分别考虑 X 和 Y，因为它们彼此独立地增加距离。这将问题简化为在给定一条线上的 n 个点的情况下，找到一个与其他点的距离之和最小的点。这很简单：两个中位数（包括）之间的任何点都将满足这一点。
证明：如果我们有偶数个点，将有两个中位数。两个中位数之间的点将在左侧有 n/2 个点，在右侧有 n/2 个点，以及到 S 的这些点的总距离和。
如果我们将它向左移动一点，S 将上升 n/2 （因为我们正在远离最右边的点）并下降 n/2 （因为我们正在向最左边的点移动)，所以整体 S 保持不变。在我们达到最左边的中点之前，这都是正确的。当我们将最左边的中间点向左移动时，我们现在有 (n/2 + 1) 个点向右，(n/2 - 1) 个点向左，所以 S 上升了 2。继续向左只会进一步增加S。
同样的逻辑，最右边中位数右边的所有点也有一个更高的 S。
如果我们有奇数个点，则只有一个中位数。使用与上述相同的逻辑，我们可以证明它具有最低的 S 值。
如果中位数为您提供 10^9 数量级的区间，则该区间中的每个点都与其他点一样好。
因此，根据您以后想要对这些点做什么，您可以返回范围或枚举该范围内的点。没办法。。
显然，在二维中你会得到一个边界矩形，在 3 维中你会得到一个边界长方体等。
结果将始终是为每个维度获得的范围的笛卡尔积，因此您可以返回这些范围的列表作为结果。
由于在曼哈顿距离中，每个组件都是单独贡献的，因此您也可以单独考虑它们。最佳答案是（中位数（x），中位数（y））。您需要在这一点上寻找整数解决方案。
注意：我在回答时没有正确阅读您的问题。我的回答仍然成立，但您可能已经知道这个解决方案。
是的，我还认为，对于网格上的奇数 N 个点，将只有一个点（即 MEDIAN），它与所有其他点的曼哈顿距离之和最小。
对于 N 的偶数值，情况会有所不同。
根据我的说法，如果两个集合，X = {1,2} and Y= {3,4}他们的笛卡尔积将始终为 4。
即X × Y = {1,2} × {3,4} = {(1,3), (1,4), (2,3), (2,4)}。这是我到目前为止所理解的。
至于偶数个值，我们总是将“中间两个”值作为 MEDIAN。从 X 中取 2 并从 Y 中取 2 将始终返回 4 点的笛卡尔积。
如果我错了，请纠正我。