安装栅栏 II

本题解采用了Welzl算法，这是一个递归算法，用于找到覆盖给定点集的最小圆。算法的基本思想是，开始假设没有点在圆内，逐步添加点，并调整圆的位置和大小以包含所有点。如果添加的点已在圆内，则不需要调整；如果不在圆内，该点必在新的圆的边界上，此时需要重新计算圆。算法具体包括以下步骤： 1. 随机化点的顺序，以避免特定边界情况影响性能。 2. 使用两点确定一个圆，计算圆心和半径。 3. 使用三点确定一个圆，确保这三点不共线，计算圆心和半径。 4. 递归地检查每个点，如果点在当前圆外，则更新圆，使其包括该点，这可能需要找到新的两点或三点定圆。

时间复杂度: O(n^3)

空间复杂度: O(n)

class Solution:
    def outerTrees(self, trees: List[List[int]]) -> List[float]:  
        n = len(trees)
        # 随机化点防止恶心用例
        random.shuffle(trees)
                                      
        # 求两点距离的平方
        def getDist(a,b,x,y):
            return (a-x)*(a-x)+(b-y)*(b-y)
                              
        # 根据两点求圆心和半径
        def getCircleBy2(i,j):
            a,b = trees[i]
            x,y = trees[j]
            rx,ry = (a+x)/2,(b+y)/2
            r = getDist(rx,ry,x,y)
            return [rx,ry,r]               
        
        # 根据三个点求圆心和半径，保证三点不共线              
        def getCircleBy3(i,j,h):
            x,y = trees[i]
            a,b = trees[j]
            p,q = trees[h]            
            
            if a == x:
                k1 = float('inf')
            else:
                k1 = (y-b)/(x-a)
            
            if x == p:
                k2 = float('inf')
            else:
                k2 = (q-y)/(p-x)
            
            # 同斜率，三点共线 
            if k1 == k2 or abs(k1-k2) < 1e-7:
                tmp = []
                tmp.append(getCircleBy2(i,j))
                tmp.append(getCircleBy2(i,h))
                tmp.append(getCircleBy2(j,h))
                tmp.sort(key = lambda x:x[2])
                return tmp[-1]
                
            # 不同斜率，选取两直线，其中垂线斜率要存在的，然后求出两中垂线交点，即为圆心
            # 保证中垂线有斜率
            if b == y:
                x,y,p,q = p,q,x,y
            elif y == q:
                a,b,x,y = x,y,a,b
                       
            
            # a,b,x,y 中垂线            
            k1 = -(x-a)/(y-b)            
            tmpx,tmpy = (a+x)/2,(b+y)/2
            b1 = tmpy - tmpx*k1
                       
            # x,y,p,q 中垂线
            k2 = -(x-p)/(y-q)
            tmpx,tmpy = (p+x)/2,(q+y)/2
            b2 = tmpy - tmpx*k2
            
            # y = k1*x+b1
            # y = k2*x+b2
            # (k1-k2)x + b1 - b2 = 0                                                                  
            X = (b2-b1)/(k1-k2)              
            Y = k1*X+b1
            r = ((X-x)*(X-x)+(Y-y)*(Y-y))
            return [X,Y,r]
        
        # 初始化，第一个点为圆心，半径为0
        x,y = trees[0]
        r = 0
        # welzl 算法，当前k个点在圆内，若第k+1个点不在圆内，那么第k+1个点必在圆上
        for i in range(1,n):
            a,b = trees[i]
            # 在圆内
            if getDist(x,y,a,b) <= r:
                continue
            
            # 在圆外，那么i点必定在圆上
            # 重新找圆，已知i必在圆上
            x,y = trees[i]
            r = 0
            
            # 找第二个必在圆上的点
            for j in range(i):
                a,b = trees[j]
                # 在圆上
                if getDist(x,y,a,b) <= r:
                    continue
                
                # 在圆外，那么j必在圆上，已知i也必在圆上，那就两点为圆直径，更新圆
                x,y,r = getCircleBy2(i,j)
                
                # 找第三个必在圆上的点
                for h in range(j):
                    a,b = trees[h]
                    if getDist(x,y,a,b) <= r:
                        continue
                    
                    # 在圆外，那么h必在圆上，即i,j,h必在圆上，更新圆
                    x,y,r = getCircleBy3(i,j,h)
        
        return [x,y,r**0.5]