Best Position for a Service Centre LeetCode solution in C++

1
class Solution {
2
 public:
3
  const double MIN_STEP = 0.000001; // With 0.00001 not AC
4

5
  const int dx[4] = {0, 0, 1, -1};
6
  const int dy[4] = {1, -1, 0, 0};
7

8
  double totalDist(vector<vector<int>> &positions, double cx, double cy) {
9
    double dist = 0;
10
    for (auto p : positions) {
11
      dist += hypot(p[0] - cx, p[1] - cy);
12
    }
13
    return dist;
14
  }
15

16
  double getMinDistSum(vector<vector<int>> &positions) {
17
    int n = (int)positions.size();
18
    double cx = 0, cy = 0;
19
    for (auto p : positions) {
20
      cx += p[0], cy += p[1];
21
    }
22
    cx /= n, cy /= n;
23

24
    pair<double, double> minDistCenter = {cx, cy};
25
    double minDist = totalDist(positions, cx, cy);
26
    // printf("cx = %.4lf, cy = %.4lf, minDist = %.4lf\n", minDistCenter.first,
27
    // minDistCenter.second, minDist);
28

29
    double step = 50.0; // Because max value of x, y could be 100. So half of that
30
    while (step > MIN_STEP) {
31
      pair<double, double> tempCenter = minDistCenter;
32
      double tempDist = minDist;
33

34
      for (int k = 0; k < 4; k++) {
35
        double xx = minDistCenter.first + dx[k] * step;
36
        double yy = minDistCenter.second + dy[k] * step;
37
        double d = totalDist(positions, xx, yy);
38
        // printf("d = %.4lf\n", d);
39
        if (d < minDist) {
40
          tempCenter = {xx, yy};
41
          tempDist = d;
42
        }
43
      }
44
      if (minDistCenter == tempCenter) step /= 2;
45
      minDistCenter = tempCenter;
46
      minDist = tempDist;
47
    }
48
    // printf("minDist = %.4lf\n", minDist);
49
    return minDist;
50
  }
51
};