<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 math

class Solution:
    def getMinDistSum(self, positions: List[List[int]]) -> float:
        # The case for only 1 point
        if len(positions) == 1:
            return 0
        
        # Avoid divergence in denominator
        epsilon = 1E-14

        # Total distance
        def get_distance(a, b, positions):
            return math.fsum([math.sqrt((a - x)**2 + (b - y)**2) for x, y in positions])

        # Gradient of a (x)
        def grad_a(a, b, positions):
            return math.fsum([(a - x) / math.sqrt((a - x)**2 + (b - y)**2 + epsilon) for x, y in positions])
        
        # Gradient of b (y)
        def grad_b(a, b, positions):
            return math.fsum([(b - y) / math.sqrt((a - x)**2 + (b - y)**2 + epsilon) for x, y in positions])
        
        # Best parameters so far pass 55/56
        # momentum = 10 
        # Decay_rate = 5
        # max_iterations = 10000  
        # 
        n = len(positions)
        max_iterations = 10000                        # Maxiteration to avoid timeout
        decay_rate = 5                                # Deacy for momentum
        a = math.fsum([x for x, y in positions])/n    # Starting positon of x, the optimal x positon for a minimun square sum
        b = math.fsum([y for x, y in positions])/n    # Starting positon of y, the optimal y positon for a minimun square sum
        momentum = 20                                 # Momentum for gradient descent, 
        min_distance = float('inf')

        # Gradient descent with decresing momentum
        for num_iterations in range(max_iterations):
            curr_distance = math.fsum([math.sqrt((a - x)**2 + (b - y)**2) for x, y in positions])
            # Exit when stable enough
            # if math.fabs(curr_distance - min_distance) < 5E-6:
            #     min_distance = min(min_distance, curr_distance)
            #     break
            min_distance = min(min_distance, curr_distance)
            # Updata parameters
            a = a - momentum * grad_a(a, b, positions)
            b = b - momentum * grad_b(a, b, positions)

            # Decrease momentum as more interations done
            if num_iterations != 0 and num_iterations % 500 == 0: #and decay_rate >= 1E-5:
                momentum /= decay_rate

        return min_distance
        
16900