题解 P5549 【[BJ United Round #3] 观察星象】

· · 题解

算法一

显然所选的圆上要么有两个点要么有至少三个。因此分别枚举，枚举两个点作为圆的直径，此外枚举三个点之后可以确定唯一一个外接圆。

时间复杂度 \Theta(n^4)，预计得分 10\%。

算法二

首先将点的顺序打乱，考虑维护前 $k$ 个点的最小圆。可以证明前 $k+1$ 个点的最小覆盖圆由前 $k$ 个点最小覆盖圆上的关键点和第 $k+1$ 个点，新的最小覆盖圆的关键点一定在这些点之间。因此只有常数种情况，每种通过 $\Theta(n)$ 的 check 即可。第 $k$ 个点不在前 $k-1$ 个点的最小覆盖圆内的概率显然是 $O(\frac1k)$，因此第 $k$ 个点消耗的期望复杂度是 $\Theta(k) \cdot O(\frac1k) = \Theta(1)$。 期望时间复杂度 $\Theta(n)$，预计得分 $20\%$。 #### 算法三 我们考虑二分答案。那么接下来枚举哪个点在圆上，其它每个点我们可以计算出它对于当前圆在哪个夹角区间内，进行一遍前缀和即可查找出是否存在一个夹角使得该圆包含 $m$ 个点。 时间复杂度 $\Theta(n^2\log n \log \frac{x}{\epsilon})$，预计得分 $60\%$。 #### 算法四 我们对算法三进行进一步的观察。事实上我们可以看成这样一个问题，对于第 $i$ 个点，客观上存在一个 $r_i$ 即最小的圆的半径使得圆内有 $m$ 个点（我们认为无解即 $+\infty$），我们在二分的过程中，总共会预计调用 $\Theta(n\log \frac{x}{\epsilon})$ 次检查。这实际上是有所浪费的，在同样的检查次数内，实际上我们还可以算出每个 $i$ 对应的 $r_i$，换句话说我们多获取了不必要的信息，因为我们只关心最小值。 接下来就是有趣的地方了：我们先将序列随机打乱，并把当前最小值设为 $a = +\infty$。接下来我们将点一个个考虑，我们实际上可以一次检查出当前点的答案是否可以 $< a$。如果并不小于，我们就可以略过它，否则对该点的答案进行二分。这样显然是进行 $n + L\log \frac{x}{\epsilon}$ 次检查，其中 $L$ 是 $r_i$ 序列的单调栈长度。 显然最坏情况是 $r$ 互不相同时，单调栈长度的期望最长，这等价于一个排列的期望长度。而这一期望长度等于 $H_n = \sum_{k=1}^n \frac 1k = \Theta(\log n)$。 因此本算法的期望复杂度为 $\Theta( (n + \log n \log \frac{x}{\epsilon}) n\log n)$，预计得分 $100\%$。