Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1515.html
1515. Best Position for a Service Centre (Hard)
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 <= 50positions[i].length == 20 <= positions[i][0], positions[i][1] <= 100
Related Topics: Geometry
Solution 1. Simulated Annealing
Starting from a random point (here I use (0, 0)). We move around in 4 directions with some initial step (I used 100).
If we can find smaller total distance, we move to that point.
Otherwise, we set step /= 2.
We keep this iteration until the step is smaller than 1e-6.
See more:
- https://stackoverflow.com/questions/12934213/how-to-find-out-geometric-median
- https://en.wikipedia.org/wiki/Geometric_median
// OJ: https://leetcode.com/problems/best-position-for-a-service-centre/
// Time: O(N * S) where S is the steps taken to reach the center
// Space: O(1)
class Solution {
double dist(vector<int> &a, vector<double> &b) {
return sqrt(pow(a[0] - b[0], 2) + pow(a[1] - b[1], 2));
}
double all(vector<vector<int>> &A, vector<double> &p) {
double ans = 0;
for (auto &a : A) ans += dist(a, p);
return ans;
}
const int dirs[4][2] = { {0,1},{0,-1},{-1,0},{1,0} };
public:
double getMinDistSum(vector<vector<int>>& A) {
double ans = DBL_MAX, step = 100, eps = 1e-6;
vector<double> p(2, 0);
while (step > eps) {
bool found = false;
for (auto &dir : dirs) {
vector<double> next = {p[0] + step * dir[0], p[1] + step * dir[1]};
double d = all(A, next);
if (d < ans) {
ans = d;
p = next;
found = true;
break;
}
}
if (!found) step /= 2;
}
return ans;
}
};
Other Solutions
- https://leetcode.com/problems/best-position-for-a-service-centre/discuss/731577/C%2B%2B-with-picture-zoom-in
-
class Solution { public double getMinDistSum(int[][] positions) { int length = positions.length; if (length == 1) return 0; double xCentre = -1, yCentre = -1; final double EPSILON = 1e-6; double difference = 1; while (difference > EPSILON) { double xNumerator = 0, yNumerator = 0, denominator = 0; for (int[] position : positions) { double distance = euclideanDistance(xCentre, yCentre, position[0], position[1]); if (distance != 0) { xNumerator += position[0] / distance; yNumerator += position[1] / distance; denominator += 1 / distance; } } if (denominator == 0) break; double xCentreNew = xNumerator / denominator, yCentreNew = yNumerator / denominator; difference = euclideanDistance(xCentre, yCentre, xCentreNew, yCentreNew); xCentre = xCentreNew; yCentre = yCentreNew; } double distanceSum = 0; for (int[] position : positions) distanceSum += euclideanDistance(xCentre, yCentre, position[0], position[1]); return distanceSum; } public double euclideanDistance(double x0, double y0, double x1, double y1) { return Math.sqrt((x1 - x0) * (x1 - x0) + (y1 - y0) * (y1 - y0)); } } -
// OJ: https://leetcode.com/problems/best-position-for-a-service-centre/ // Time: O(N * S) where S is the steps taken to reach the center // Space: O(1) class Solution { double dist(vector<int> &a, vector<double> &b) { return sqrt(pow(a[0] - b[0], 2) + pow(a[1] - b[1], 2)); } double all(vector<vector<int>> &A, vector<double> &p) { double ans = 0; for (auto &a : A) ans += dist(a, p); return ans; } const int dirs[4][2] = { {0,1},{0,-1},{-1,0},{1,0} }; public: double getMinDistSum(vector<vector<int>>& A) { double ans = DBL_MAX, step = 100, eps = 1e-6; vector<double> p(2, 0); while (step > eps) { bool found = false; for (auto &dir : dirs) { vector<double> next = {p[0] + step * dir[0], p[1] + step * dir[1]}; double d = all(A, next); if (d < ans) { ans = d; p = next; found = true; break; } } if (!found) step /= 2; } return ans; } }; -
class Solution: def getMinDistSum(self, positions: List[List[int]]) -> float: n = len(positions) x = y = 0 for x1, y1 in positions: x += x1 y += y1 x, y = x / n, y / n decay = 0.999 eps = 1e-6 alpha = 0.5 while 1: grad_x = grad_y = 0 dist = 0 for x1, y1 in positions: a = x - x1 b = y - y1 c = sqrt(a * a + b * b) grad_x += a / (c + 1e-8) grad_y += b / (c + 1e-8) dist += c dx = grad_x * alpha dy = grad_y * alpha x -= dx y -= dy alpha *= decay if abs(dx) <= eps and abs(dy) <= eps: return dist -
func getMinDistSum(positions [][]int) float64 { n := len(positions) var x, y float64 for _, p := range positions { x += float64(p[0]) y += float64(p[1]) } x /= float64(n) y /= float64(n) const decay float64 = 0.999 const eps float64 = 1e-6 var alpha float64 = 0.5 for { var gradX, gradY float64 var dist float64 for _, p := range positions { a := x - float64(p[0]) b := y - float64(p[1]) c := math.Sqrt(a*a + b*b) gradX += a / (c + 1e-8) gradY += b / (c + 1e-8) dist += c } dx := gradX * alpha dy := gradY * alpha if math.Abs(dx) <= eps && math.Abs(dy) <= eps { return dist } x -= dx y -= dy alpha *= decay } } -
function getMinDistSum(positions: number[][]): number { const n = positions.length; let [x, y] = [0, 0]; for (const [px, py] of positions) { x += px; y += py; } x /= n; y /= n; const decay = 0.999; const eps = 1e-6; let alpha = 0.5; while (true) { let [gradX, gradY] = [0, 0]; let dist = 0; for (const [px, py] of positions) { const a = x - px; const b = y - py; const c = Math.sqrt(a * a + b * b); gradX += a / (c + 1e-8); gradY += b / (c + 1e-8); dist += c; } const dx = gradX * alpha; const dy = gradY * alpha; if (Math.abs(dx) <= eps && Math.abs(dy) <= eps) { return dist; } x -= dx; y -= dy; alpha *= decay; } }