A delivery company wants to build a new service centre in a new city. The company knows the positions of all the customers in this city on a 2D-Map and wants to build the new centre in a position such that the sum of the euclidean distances to all customers is minimum.
Given an array positions
where positions[i] = [xi, yi]
is the position of the ith
customer on the map, return the minimum sum of the euclidean distances to all customers.
In other words, you need to choose the position of the service centre [xcentre, ycentre]
such that the following formula is minimized:
Answers within 10^-5
of the actual value will be accepted.
Example 1:
Input: positions = [[0,1],[1,0],[1,2],[2,1]] Output: 4.00000 Explanation: As shown, you can see that choosing [xcentre, ycentre] = [1, 1] will make the distance to each customer = 1, the sum of all distances is 4 which is the minimum possible we can achieve.
Example 2:
Input: positions = [[1,1],[3,3]] Output: 2.82843 Explanation: The minimum possible sum of distances = sqrt(2) + sqrt(2) = 2.82843
Example 3:
Input: positions = [[1,1]] Output: 0.00000
Example 4:
Input: positions = [[1,1],[0,0],[2,0]] Output: 2.73205 Explanation: At the first glance, you may think that locating the centre at [1, 0] will achieve the minimum sum, but locating it at [1, 0] will make the sum of distances = 3. Try to locate the centre at [1.0, 0.5773502711] you will see that the sum of distances is 2.73205. Be careful with the precision!
Example 5:
Input: positions = [[0,1],[3,2],[4,5],[7,6],[8,9],[11,1],[2,12]] Output: 32.94036 Explanation: You can use [4.3460852395, 4.9813795505] as the position of the centre.
Constraints:
1 <= positions.length <= 50
positions[i].length == 2
0 <= positions[i][0], positions[i][1] <= 100
Solution: Weiszfeld’s algorithm
Use Weiszfeld’s algorithm to compute geometric median of the samples.
Time complexity: O(f(epsilon) * O)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
template<typename T1, typename T2> double dist(const vector<T1>& a, const vector<T2>& b) { return sqrt((a[0] - b[0]) * (a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1])); }; class Solution { public: double getMinDistSum(vector<vector<int>>& positions) { constexpr double kDelta = 1e-7; constexpr double kEpsilon = 1e-15; vector<double> c{-1, -1}; double ans = 0; while (true) { ans = 0; double nx = 0, ny = 0; double denominator = 0; for (const auto& p : positions) { double d = dist(c, p) + kEpsilon; ans += d; nx += p[0] / d; ny += p[1] / d; denominator += 1.0 / d; } vector<double> t{nx / denominator, ny / denominator}; if (dist(c, t) < kDelta) return ans; c = t; } return -1; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment