best-position-for-a-service-centre

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

Algorithms

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 <code>positions</code> where <code>positions[i] = [xi, yi]</code> is the position of the <code>ith</code> 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 <code>[xcentre, ycentre]</code> such that the following formula is minimized:
<img alt="" src="https://assets.leetcode.com/uploads/2020/06/25/q4_edited.jpg" />
Answers within <code>10-5</code> of the actual value will be accepted.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2020/06/25/q4_e1.jpg" style="width: 377px; height: 362px;" />
<pre>
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.
</pre>

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

&nbsp;
Constraints:

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