<p>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 <strong>the sum of the euclidean distances to all customers is minimum</strong>.</p>

<p>Given an array <code>positions</code> where <code>positions[i] = [x<sub>i</sub>, y<sub>i</sub>]</code> is the position of the <code>ith</code> customer on the map, return <em>the minimum sum of the euclidean distances</em> to all customers.</p>

<p>In other words, you need to choose the position of the service center <code>[x<sub>centre</sub>, y<sub>centre</sub>]</code> such that the following formula is minimized:</p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/06/25/q4_edited.jpg" />
<p>Answers within <code>10<sup>-5</sup></code> of the actual value will be accepted.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/06/25/q4_e1.jpg" style="width: 377px; height: 362px;" />
<pre>
<strong>Input:</strong> positions = [[0,1],[1,0],[1,2],[2,1]]
<strong>Output:</strong> 4.00000
<strong>Explanation:</strong> As shown, you can see that choosing [x<sub>centre</sub>, y<sub>centre</sub>] = [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.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/06/25/q4_e3.jpg" style="width: 419px; height: 419px;" />
<pre>
<strong>Input:</strong> positions = [[1,1],[3,3]]
<strong>Output:</strong> 2.82843
<strong>Explanation:</strong> The minimum possible sum of distances = sqrt(2) + sqrt(2) = 2.82843
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= positions.length &lt;= 50</code></li>
	<li><code>positions[i].length == 2</code></li>
	<li><code>0 &lt;= x<sub>i</sub>, y<sub>i</sub> &lt;= 100</code></li>
</ul>

import numpy as np


class Solution:
    def getMinDistSum(self, positions: List[List[int]]) -> float:

        X = np.array(positions,dtype = np.float64)
        dec = 6
        max_iterations = 1000

        # Define the score (objective) function that we want to minimize
        def score(x):
            return np.sum(np.sqrt(np.sum((x - X) ** 2, axis=1)))

        # Initialize the centroid as the mean of the points
        x = X.mean(axis=0)
        
        # Perturb y slightly to avoid singularity at the start
        x[1] += 0.1  
        ans = score(x)

        scale = 1.0
        iteration = 0

        while scale > 1e-10 and iteration < max_iterations:
            # Compute distances from current point x to all points in X
            norm = np.sqrt(np.sum((x - X) ** 2, axis=1))

            # If all points are coincident, stop
            if np.sum(norm) == 0:
                return x

            # Compute the gradient (direction of steepest descent)
            grad = np.sum((x - X) / norm[:, np.newaxis], axis=0)
            grad /= np.linalg.norm(grad)  # Normalize gradient
            
            # Check if the gradient leads to improvement
            new_score = score(x - scale * grad)

            while new_score >= ans and scale > 1e-10:
                # Decrease step size if no improvement
                scale *= 0.9
                new_score = score(x - scale * grad)

            if scale > 1e-10:
                # Update solution
                x -= scale * grad
                ans = new_score

            # Increment the iteration counter
            iteration += 1

            # Optional: print information for debugging purposes
            print(f"Iteration {iteration}: scale={scale:.6f}, score={ans:.6f}, x={x}")

        return np.round(ans, decimals=dec)  # Return the centroid rounded to `dec` decimals





        # X = np.array(positions,dtype = np.float64)
        # precision = 10**(-7)
        # eta = 1
        # learning_rate = .99
        # terminal_eta = 10**(-7)
        # max_iterations = 1000
        # if max_iterations == None:
        #     max_iterations = float('inf')


        
        # def score(x):
        #     return np.sum(np.sqrt(np.sum((x-X)**2,axis = 1)),axis = 0)
        
        # x = np.mean(X,axis = 0)
        # old_score = score(x)

        # count = 0
        # while count<max_iterations:
        #     count += 1
            
        #     norm = np.sqrt(np.sum((x-X)**2,axis = 1))

        #     if np.sum(norm,axis = 0) == 0:
        #         return old_score

        #     grad = norm.dot(x-X)

        #     while score(x-eta*grad)>old_score and eta>terminal_eta:
        #         eta *= learning_rate
        #         if eta<terminal_eta:
        #             eta = terminal_eta
        #     temp_score = old_score
        #     old_score = score(x-eta*grad)
        #     x -= eta*grad
            
        #     print(eta,old_score)


        #     if abs(old_score-temp_score)<precision/200:
        #         print(x)
        #         return old_score
        # return old_score
        
28900