1924. 安装栅栏 II 🔒

难度困难

题目描述

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

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

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

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

示例 1:

输入: trees = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]
输出: [2.00000,2.00000,2.00000]
解释: 栅栏的圆心应当在 (2, 2) 处，半径为 2。

示例 2:

输入: trees = [[1,2],[2,2],[4,2]]
输出: [2.50000,2.00000,1.50000]
解释: 栅栏的圆心应当在 (2.5, 2) 处，半径为 1.5。

提示:

思考

所求为覆盖全部点的最小圆。枚举直径或三点定圆可达 \(O(n^3)\)，\(n\le 3000\) 偏紧。

最小覆盖圆由边界上两点（直径）或三点确定，Welzl 随机增量算法在期望线性时间内求出：若新点已在当前圆内则不变，否则该点必在新圆边界上，于是递归缩小点集。

实现时打乱点序并维护当前圆心与半径，误差按题面允许的 \(10^{-5}\) 控制。

Python3JavaC++Go