最小圆覆盖

例题 #1 题目描述

给出 \(N\) 个点，让你画一个最小的包含所有点的圆。

输入格式

第一行一个整数 \(N\) 表示点的个数。

接下来 \(N\) 行每行两个实数 \(x_i,y_i\) 表示点的坐标。最多两位小数。

输出格式

第一行一个实数表示圆的半径。

第二行两个实数表示圆心的坐标。

本题开启 spj，您的答案与标准答案误差不超过 \(10^{-9}\) 时，视为正确。

对于 \(100\%\) 的数据，\(1\leq N\leq 10^5\)，\(|x_i|,|y_i|\leq 10^4\)。

2022.2.26 添加 spj

---

随机化算法降低时间复杂度

首先我们考虑确定一个远的定理：三点定圆。

所以我们先从小到大枚举点i。并且实时维护当前的圆。

• 若当前枚举到的i在圆内，继续

• 如果不在，随机枚举一个i之前的点j，确定出一个最小圆C，然后再枚举一个j之前且不在圆C内的点，确定最终的圆，并且要求这个圆包含所有的点。

这个算法看似是 \(O(n^3)\)的，但是因为做了随机化，所以是O(n)的。

证明不会。

随机增量算法

快速判断一个圆C是否包含前i个点：