A delivery company wants to build a new service center 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 center 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 center [xcentre, ycentre] such that the following formula is minimized:

Answers within 10-5 of the actual value will be accepted.

&nbsp;
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


&nbsp;
Constraints:


	1 &lt;= positions.length &lt;= 50
	positions[i].length == 2
	0 &lt;= xi, yi &lt;= 100


class Solution:
    def getMinDistSum(self, positions: List[List[int]]) -> float:
        n = len(positions)
        if n == 1: return 0
        def gradient(x,y):
            ans = [0,0]
            for i in range(n):
                denom = math.sqrt(pow(x-positions[i][0],2)+pow(y-positions[i][1],2))
                ans[0] += (x-positions[i][0])/denom if denom else 0
                ans[1] += (y-positions[i][1])/denom if denom else 0
            return ans
        def fn(x, y):
            res = 0
            for i in range(n):
                res += math.sqrt(pow(x-positions[i][0],2)+pow(y-positions[i][1],2))
            return res
        x = sum(x for x,_ in positions)/n
        y = sum(y for _,y in positions)/n
        lr = 1
        while lr > 1e-7:
            dx, dy = gradient(x,y)
            x -= lr*dx
            y -= lr*dy
            lr *= 0.997
            if not dx and not dy:
                lr /= 2
        return fn(x,y)
class Solution {
    private static final double MIN_STEP = 0.0000001;
    private static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public double getMinDistSum(int[][] positions) {
        double cx = 0, cy = 0;
        int n = positions.length;
        for (int[] pos: positions) {
            cx += pos[0];
            cy += pos[1];
        }
        cx /= n; cy /= n;
        Node center = new Node(cx, cy, totalDistance(positions, cx, cy));

        double step = 50.0;
        while (step > MIN_STEP) {
            Node min = center;
            for (int[] direction: DIRECTIONS) {
                double dx = center.x + direction[0] * step, dy = center.y + direction[1] * step;
                double totalDist = totalDistance(positions, dx, dy);
                if (totalDist < center.dist) min = new Node(dx, dy, totalDist);
            }
            if (center == min) step /= 2;
            center = min;
        }

        return center.dist;
    }

    private double sq(double p) {
        return p * p;
    }

    private double dist(int[] pos, double x, double y) {
        return Math.sqrt(sq(x - pos[0]) + sq(y - pos[1]));
    }

    private double totalDistance(int[][] positions, double x, double y) {
        double dist = 0;
        for (int[] pos: positions) dist += dist(pos, x, y);
        return dist;
    }

    private static class Node {
        double x, y, dist;
        Node (double x, double y, double dist) {
            this.x = x;
            this.y = y;
            this.dist = dist;
        }
    }
}
class Solution {
public:
    const double MIN_STEP = 0.000001; // With 0.00001 not AC

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

    double totalDist(vector<vector<int>>& positions, double cx, double cy) {
        double dist = 0;
        for (auto p : positions) {
            dist += hypot(p[0] - cx, p[1] - cy);
        }
        return dist;
    }

    double getMinDistSum(vector<vector<int>>& positions) {
        int n = (int)positions.size();
        double cx = 0, cy = 0;
        for (auto p : positions) { cx += p[0], cy += p[1]; }
        cx /= n, cy /= n;

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

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

            for (int k = 0; k < 4; k++) {
                double xx = minDistCenter.first + dx[k] * step;
                double yy = minDistCenter.second + dy[k] * step;
                double d = totalDist(positions, xx, yy);
                //printf("d = %.4lf\n", d);
                if (d < minDist) {
                    tempCenter = {xx, yy};
                    tempDist = d;
                }
            }
            if (minDistCenter == tempCenter) step /= 2;
            minDistCenter = tempCenter;
            minDist = tempDist;
        }
        //printf("minDist = %.4lf\n", minDist);
        return minDist;
    }
};
/**
 * @param {number[][]} positions
 * @return {number}
 */
var getMinDistSum = function(positions) {
    /**
      identify the vertical range and horizontal range
      
      start from the center of positions
      calc the distance
        test the 4 direction with a certain step
            if any distance is closer, choose it as the new candidate
        if all 4 are further, reduce the step
    **/
    
    
    let xSum = 0;
    let ySum = 0;
    for (const [x, y] of positions) {
        xSum += x;
        ySum += y;
    }
    
    let n = positions.length;
    let x = xSum / n;
    let y = ySum / n;
    
    let step = 0.5;
    const dirs = [[0, 1], [0, -1], [-1, 0], [1, 0]];
    while (step >= 10 ** -5) {
        
        const dist = calcDist(x, y);
        let found = false;
        for (const [xDiff, yDiff] of dirs) {
            const newX = x + xDiff * step;
            const newY = y + yDiff * step;
            const newDist = calcDist(newX, newY);
            
            // console.log(x, y, newDist, dist);
            if (newDist < dist) {
                x = newX;
                y = newY;
                found = true;
                break;
            }
        }
        
        if (!found) {
            step /= 2;
        }
    }
    
    return calcDist(x, y);
    
    
    function calcDist(x, y) {
        let dist = 0;
        for (const [posX, posY] of positions) {
            dist += Math.sqrt((x - posX) ** 2 + (y - posY) ** 2);
        }
        return dist;
    }
};
Best Position for a Service Centre