# 1515. Best Position for a Service Centre¶

• Time:
• Space:
  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 31 32 33 34 35 36 37 38 class Solution { public: double getMinDistSum(vector>& positions) { constexpr double kErr = 1e-6; double currX = 50; double currY = 50; double ans = distSum(positions, currX, currY); double step = 1; while (step > kErr) { bool shouldDecreaseStep = true; for (const auto& [dx, dy] : vector>{ {0, step}, {0, -step}, {step, 0}, {-step, 0}}) { const double x = currX + dx; const double y = currY + dy; const double newDistSum = distSum(positions, x, y); if (newDistSum < ans) { ans = newDistSum; currX = x; currY = y; shouldDecreaseStep = false; } } if (shouldDecreaseStep) step /= 10; } return ans; } private: double distSum(const vector>& positions, double a, double b) { double sum = 0; for (const vector& p : positions) sum += sqrt(pow(a - p[0], 2) + pow(b - p[1], 2)); return sum; } }; 
  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 31 32 33 34 35 class Solution { public double getMinDistSum(int[][] positions) { final double kErr = 1e-6; double currX = 50; double currY = 50; double ans = distSum(positions, currX, currY); double step = 1; while (step > kErr) { boolean shouldDecreaseStep = true; for (double[] dirs : new double[][] {{0, step}, {0, -step}, {step, 0}, {-step, 0}}) { final double x = currX + dirs[0]; final double y = currY + dirs[1]; final double newDistSum = distSum(positions, x, y); if (newDistSum < ans) { ans = newDistSum; currX = x; currY = y; shouldDecreaseStep = false; } } if (shouldDecreaseStep) step /= 10; } return ans; } private double distSum(int[][] positions, double a, double b) { double sum = 0; for (int[] p : positions) sum += Math.sqrt(Math.pow(a - p[0], 2) + Math.pow(b - p[1], 2)); return sum; } } 
  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 class Solution: def getMinDistSum(self, positions: List[List[int]]) -> float: def distSum(a: float, b: float) -> float: return sum(math.sqrt((a - x)**2 + (b - y)**2) for x, y in positions) kErr = 1e-6 currX = 50 currY = 50 ans = distSum(currX, currY) step = 1 while step > kErr: shouldDecreaseStep = True for dx, dy in [(0, step), (0, -step), (step, 0), (-step, 0)]: x = currX + dx y = currY + dy newDistSum = distSum(x, y) if newDistSum < ans: ans = newDistSum currX = x currY = y shouldDecreaseStep = False if shouldDecreaseStep: step /= 10 return ans