所有点都具有最小曼哈顿距离与所有其他已知点[优化] [英] All points with minimum Manhattan distance from all other given points [Optimized]

问题描述

这里的问题是要找到设置所有整数点赋予最小和在从给定的点集所有曼哈顿距离的<！/ P>

例如：

让有一组给定的点{P1，P2，P3 ... PN}

的

基本问题是要找到一个点说，x，它会具有最小的总和由点所有距离{P1，P2，P3 ... PN}。

即。 | P1-X | + | P2-X | + ... + |光合-X | = D，其中D为最小过所有的X。

移动了一步，也可以是第X满足上述条件一个以上的值。即超过一个X可以是可能的，这些将给予同​​样的值D所以，我们需要找到所有这样的X.

一个基本的方法，任何人都可以想到的将是找到的输入值，然后强力其中提到的这个帖子

不过，这种方法的问题是：如果中给出了两个值，这是非常分开，那么我们就结束了暴力破解所有的点，这将永远不会在给定的时间运行

那么，有没有这将使结果即使在点相距甚远（其中位数给出一个范围是10 ^ 9级）其他方式。

解决方案

如果中位数为您提供了10 ^ 9量级的间隔，然后在该区间内的各点不如其他。

所以，这取决于你希望以后做的这些点上，你可以返回范围或枚举点在这个范围内的东西。没有办法解决它。

显然，在两个维度上，你会得到一个bouding矩形，在3维的边界长方体等。

结果将永远是每个维度所得范围的笛卡尔积，这样你就可以返回这些范围的列表作为结果。

The problem here is to find set of all integer points which gives minimum sum over all Manhattan distances from given set of points!

For example:

lets have a given set of points { P1, P2, P3...Pn }

Basic problem is to find a point say X which would have minimum sum over all distances from points { P1, P2, P3... Pn }.

i.e. |P1-X| + |P2-X| + .... + |Pn-X| = D, where D will be minimum over all X.

Moving a step further, there can be more than one value of X satisfying above condition. i.e. more than one X can be possible which would give the same value D. So, we need to find all such X.

One basic approach that anyone can think of will be to find the median of inputs and then brute force the co-ordinates which is mentioned in this post

But the problem with such approach is: if the median gives two values which are very apart, then we end up brute forcing all points which will never run in given time.

So, is there any other approach which would give the result even when the points are very far apart (where median gives a range which is of the order of 10^9).

解决方案

If the median gives you an interval of the order of 10^9 then each point in that interval is as good as any other.

So depending on what you want to do with those points later on you can either return the range or enumerate points in that range. No way around it..

Obviously in two dimensions you'll get a bouding rectangle, in 3 dimensions a bounding cuboid etc..

The result will always be a cartesian product of ranges obtained for each dimension, so you can return a list of those ranges as a result.

这篇关于所有点都具有最小曼哈顿距离与所有其他已知点[优化]的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！