Leetcode 1638 Solution

This article provides solution to leetcode question 1638 (best-position-for-a-service-centre)
Categories:
Tags:
Access this page by simply typing in "lcs 1638" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/best-position-for-a-service-centre

Solution

class Solution:
    def getMinDistSum(self, positions: List[List[int]]) -> float:
        def evaluate(x, y):
            nonlocal positions
            return sum(math.sqrt((x - px) ** 2 + (y - py) ** 2) for px, py in positions)

        step = 1
        x = 0
        y = 0
        while step > 0.00001:
            found = False

            val = evaluate(x, y)
            if evaluate(x + step, y) < evaluate(x, y):
                found = True
                x = x + step
            if evaluate(x, y + step) < evaluate(x, y):
                found = True
                y = y + step
            if evaluate(x - step, y) < evaluate(x, y):
                found = True
                x = x - step
            if evaluate(x, y - step) < evaluate(x, y):
                found = True
                y = y - step

            if not found:
                step /= 2

        return evaluate(x, y)