当前位置：首页 > web >正文

Leetcode 1924. 安装栅栏 II

web 2025/7/28 4:58:20

1.题目基本信息

1.1.题目描述

给你一个二维整数数组 trees，其中 trees[i] = [xi, yi] 表示花园中第 i 棵树的坐标。

你需要用最少的原材料给花园安装一个圆形的栅栏，使花园中所有的树都在被围在栅栏内部（在栅栏边界上的树也算在内）。

正式地说，你需要求出栅栏的圆心坐标 (x,y) 和半径 r，使花园中所有的树都在圆的内部或边界上，并且让半径 r 最小。

请用一个长度为 3 的数组 [x,y,r] 来返回圆心坐标和半径。如果答案与正确答案的误差不超过 10-5，则该答案将被视为正确答案通过。

1.2.题目地址

https://leetcode.cn/problems/erect-the-fence-ii/description/

2.解题方法

2.1.解题思路

welzl算法

2.2.解题步骤

第一步，将坐标点随机打乱，并将tree中的各个结点转换成Point对象

第二步，构建维护变量。center和r2维护当前最小圆的中心坐标点和半径的平方。初始化第一个结点为中心且r2=0

第三步，枚举结点组合+剪枝，更新center和r2直到结束

3.1.假设当前的最小圆为(center,r2)，枚举当前结点，如果当前结点i在(center,r2)圆内，不用继续剩下的二层循环，直接跳到下一个结点
3.2.如果当前结点i不在(center,r2)最小圆中，则将i结点作为圆心（初始半径为0），在保证结点i在最小圆的边上的情况下，枚举i前面的结点的两两组合（双层循环），记两个结点为j和k，并进行最小圆
3.3.剪枝。如果第二层循环的结点j没在圆中，那么将i和j两个结点作为直径构建最小圆。反之枚举第三个结点k，如果第三个点没在最小圆中，则用这三个点构建圆并更新(center,r2)最小圆信息。最终这种枚举一定会枚举到最外围构建的最小圆的三个结点，所以最终结果（靶）一定是正确的

第四步，最终的center和sqrt(r)即为题解

3.解题代码

Python代码

class Point():def __init__(self, x:float, y:float):self.x = xself.y = ydef __str__(self):return f"({self.x}, {self.y})"# 工具函数：计算两点之间的距离的平方
def calcDist2(p1:Point, p2:Point) -> float:return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y)# 工具函数：根据三个顶点构建圆，分为三角形情形和共线情形，三角形情形求外心，共线情形则用相距最远的两个点作为直径建立最小圆。返回圆的中心点和半径的平方
def getCircle(p1:Point, p2:Point, p3:Point) -> (Point, float):if (p1.x - p2.x) * (p2.y - p3.y) == (p2.x - p3.x) * (p1.y - p2.y):# > 三点共线的情况points = sorted([p1, p2, p3], key = lambda p:p.x)p1 = points[0]p2 = points[2]centerPoint = Point((p1.x + p2.x) / 2, (p1.y + p2.y) / 2)r2 = calcDist2(p1, centerPoint)return centerPoint, r2else:# > 三点不平行的情况。使用圆心到三点的距离相等构建等式，然后行列式求圆心x1, y1 = p1.x, p1.yx2, y2 = p2.x, p2.yx3, y3 = p3.x, p3.ya1, b1 = x1 - x2, y1 - y2   # 方程1的系数a2, b2 = x1 - x3, y1 - y3   # 方程2的系数c1 = (x1 * x1 - x2 * x2 + y1 * y1 - y2 * y2) / 2    # 方程1右边常数c2 = (x1 * x1 - x3 * x3 + y1 * y1 - y3 * y3) / 2    # 方程2右边常数d = a1 * b2 - a2 * b1d1 = c1 * b2 - c2 * b1d2 = a1 * c2 - c1 * a2point = Point(x = d1 / d, y = d2 / d)c2 = (point.x - x1) * (point.x - x1) + (point.y - y1) * (point.y - y1)return point, c2eps = 10 ** (-9)class Solution:def outerTrees(self, trees: List[List[int]]) -> List[float]:# 思路：welzl算法# 第一步，将坐标点随机打乱，并将tree中的各个结点转换成Point对象points = [Point(x, y) for x, y in trees]# random.seed(100)random.shuffle(points)# 第二步，构建维护变量。center和r2维护当前最小圆的中心坐标点和半径的平方。初始化第一个结点为中心且r2=0center, r2 = points[0], 0# 第三步，枚举结点组合+剪枝，更新center和r2直到结束n = len(points)for i in range(1, n):# 3.1.假设当前的最小圆为(center,r2)，枚举当前结点，如果当前结点i在(center,r2)圆内，不用继续剩下的二层循环，直接跳到下一个结点pointi = points[i]# print(center, r2, pointi, calcDist2(center, pointi))if calcDist2(center, pointi) < r2 + eps:continue# 3.2.如果当前结点i不在(center,r2)最小圆中，则将i结点作为圆心（初始半径为0），在保证结点i在最小圆的边上的情况下，枚举i前面的结点的两两组合（双层循环），记两个结点为j和k，并进行最小圆center, r2 = pointi, 0for j in range(i):pointj = points[j]# print(center, r2, pointi, pointj)if calcDist2(center, pointj) < r2 + eps:continuecenter = Point((pointi.x + pointj.x) / 2, (pointi.y + pointj.y) / 2)r2 = calcDist2(center, pointi)for k in range(j):# 3.3.剪枝。如果第二层循环的结点j没在圆中，那么将i和j两个结点作为直径构建最小圆。反之枚举第三个结点k，如果第三个点没在最小圆中，则用这三个点构建圆并更新(center,r2)最小圆信息。最终这种枚举一定会枚举到最外围构建的最小圆的三个结点，所以最终结果（靶）一定是正确的pointk = points[k]# print(center, r2, pointi, pointj, pointk)if calcDist2(center, pointk) < r2 + eps:continuecenter, r2 = getCircle(pointi, pointj, pointk)# 第四步，最终的center和sqrt(r)即为题解return [center.x, center.y, sqrt(r2)]