Question

1924. 安装栅栏 II

English Version

题目描述

给你一个二维整数数组 trees，其中 trees[i] = [xi, yi] 表示花园中第 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。

 

提示:

• 1 <= trees.length <= 3000
• trees[i].length == 2
• 0 <= xi, yi <= 3000

解法