Skip to content

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<vector<int>>& 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<pair<double, double>>{
               {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<vector<int>>& positions, double a, double b) {
    double sum = 0;
    for (const vector<int>& 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