Problem statement

https://leetcode.com/problems/erect-the-fence-ii/

Solution

In this problem we are asked to find the smallest circle that cover all given points, this is very classical problem in computational geometry, it is called Smallest-circle problem. There is algorithm with different complexities and the best one is so-called Welzl algorithm with O(n) expected time of work.

Complexity

Expected time of Welzl algorithm is O(n), space is O(n) as well.

Code

class Solution:
    def outerTrees(self, trees):
        def dist(a, b):
            return ((a[0]-b[0])**2 + (a[1]-b[1])**2)**0.5

        def inside(c, p):
            return dist(c[0], p) < c[1] + eps

        def circle_2(A, B):
            I = [(A[0]+B[0])/2, (A[1]+B[1])/2]
            return [I, dist(A, B)/2]

        def circle_3(A, B, C):
            bx, by, cx, cy = B[0]-A[0], B[1]-A[1], C[0]-A[0], C[1]-A[1]
            B = bx*bx + by*by
            C = cx*cx + cy*cy
            D = bx*cy - by*cx
            I = [(cy*B - by*C)/2/D + A[0], (bx*C - cx*B)/2/D + A[1]]
            return [I, dist(I, A)]

        def trivial(bound):
            if not bound: return []
            if len(bound) == 1: return [bound[0], 0.0]
            if len(bound) == 2: return circle_2(bound[0], bound[1])
            return circle_3(bound[0], bound[1], bound[2])

        def Welzl(P, bound, curr):
            if curr == len(P) or len(bound) == 3:
                return trivial(bound)
            res = Welzl(P, bound, curr+1)
            if res and inside(res, P[curr]):
                return res
            bound.append(P[curr])
            res = Welzl(P, bound, curr+1)
            bound.pop()
            return res

        eps = 1e-5
        random.shuffle(trees)
        result = Welzl(trees, [], 0)
        return result[0][0], result[0][1], result[1]