Best Position for a Service Centre

Challenge Points: 30

Level: Hard

You are given a list of customer coordinates on a 2D map. You must choose a location for a new service center such that the sum of the Euclidean distances from the service center to every customer is as small as possible.

Formally, if the chosen point is (x, y), the cost is:

sum( sqrt((x - xi)^2 + (y - yi)^2) ) for all given points (xi, yi)

The task is to return the minimum possible sum.
Your returned value will be accepted if it differs from the actual answer by at most 1e−5.

Note: The optimal point does not always lie on one of the given customer coordinates.

Example 1:

Input: positions = [[-1,-1],[1,1],[1,-1],[-1,1]]

Output: 5.65685

Explanation:

Optimal center = (0,0)

Example 2:

Input: positions = [[0,0],[2,0],[1,1]]

Output: 2.15470

Explanation:

Optimal center ≈ (1,0.577)

to Continue

Accepted:

Submission:

Report an issue

Code

You need toto run or submitYou need toto run or submit

Test Case

Test Result