一、固定半径最少圆覆盖问题

背景：二维坐标轴中，给出n个点以及每个点的坐标（坐标为浮点型），和一个长度m（m为浮点型），求至少需要多个半径为m的圆可以把所有点覆盖住

输入：第一行输入n和m，以下2 ~ n + 1行中第 i + 1 行 输入 x_i, y_i 表示第 i 个点的坐标

输出：一个数，表示圆的个数

其中，0 < n <= 20；-180 <= x,y <= 180

根据上表，可以支持O(2ⁿ)的算法

（整活）AI组简单粗暴算法（错误算法）：

首先看看AI组给我们的代码是什么：

#include <stdio.h>
int main(){
    int n;
    float m;
    scanf("%d %f", &n, &m);
    float x[n], y[n];
    for(int i = 0; i < n; i++){
        scanf("%f %f", &x[i], &y[i]);
    }
    int count = 0;
    float cx[n], cy[n];
    for(int j = 0; j < n; j++){
        int flag = 0;
        for(int k = 0; k < count; k++){
            float distance = (x[j] - cx[k]) * (x[j] - cx[k]) + (y[j] - cy[k]) * (y[j] - cy[k]);
            if(distance <= m * m){
                flag = 1;
                break;
            }
        }
        if(flag == 0){
            cx[count] = x[j];
            cy[count] = y[j];
            count++;
        }
    }
    printf("%d", count);
    return 0;
}

时间复杂程度是O(n²)，思路很简单：枚举每一个点，求每一个已经记录的圆心到该点的距离，如果在半径内则把这个点跳过；否则就将该点作为新的圆心记录。

AI的思路非常简单粗暴，但是很明显的错误点就是把每个点都作为圆心来求解，很明显这个思路是不正确的，举个例子：如果半径长m = 1，两个点(0,0)，(0,2)很明显只需要一个圆心在(0,1)的圆就可以完全覆盖，但是如果用以上算法得出的结果是2，具体为什么自己可以思考一下。

这个算法也是大部分人第一时间会想到的算法，很明显是错误。

一开始我写的代码也是跟这个思路差不多，也无法完全处理两个点在圆的直径两边的情况。

思路一：暴力枚举  O(n⁴ )

首先每一个答案的圆心一定是某三个组成三角形的外接圆圆心 或者 两个点连成直线的中心。简单证明思路（并不能完全证明正确性）如下：

虽然给出了明确圆的半径m，但是并不一定所有圆的半径要去等于m，简单说就是同一个圆心中，半径为m和半径为i（i <= m）能覆盖相同数量的点，那么这个圆的半径是m和i都是一样的效果。

我们设相同圆心中，如果半径为m的圆与半径为i (i <= m) 的圆覆盖的点相同，则设这个半径为i的圆为半径m的 半径为i的等价圆 （下面可能直接称之为等价圆）。

那么我们可以推断出每一个最终答案的半径为m的圆必定存在一个半径为i的等价圆，该等价圆的弧线上至少存在两个点。为什么？因为如果一个圆能包含三个点，那么这个圆取最小半径的时候一定是这三个点连成的三角形的外接圆；如果一个圆能包含两个点，那么这个圆取最小半径时一定是以这两个点为直径；如果一个圆能包含多个点形成多个三角形的外接圆，那么这个圆半径最小的时候一定是其中三个点形成三角形的外接圆（论证自己想），假设这个外接圆半径i已经是可以枚举出的小于m的半径最大的，那么这个圆就是m的 半径为i的等价圆。

那么就可以给出暴力枚举的思路了：

• 维护一个队列用来储存圆（圆结构体储存圆的圆心、覆盖点的个数以及覆盖点的坐标）；首先枚举三个点（时间复杂程度为O(C_n²) = O(n³)，求出这三个点的外接圆半径，如果半径小于等于m则加入队列；枚举两个点（时间复杂程度为O(C_n²) = O(n²)），计算这两个点的直线距离除以二，如果小于m则加入队列
• 枚举每一个圆所覆盖的点的个数（时间复杂程度为O(n⁴)）（此时可以维护一个并查集，如果所有的点都已经被记录则剪枝）
• 维护一个并查集，表示点是否被连接；用Dijkstra最短路算法思想来处理最小生成树：维护一个大根堆，堆的价值为该圆的覆盖点的数量，将所有的圆塞入堆里(O(n³logn)。然后以堆是否为空做循环，取出堆首（O(1)），判断该圆的实际覆盖点的个数，也就是记录覆盖点的个数减去已经覆盖过的点个数(O(n))，如果不等于则更改覆盖点的个数重新塞入堆中(O(logn))，如果等于则进行记录并将点塞入并查集。

 综上，时间复杂程度为O(n⁴ )，在n <= 20的时候完全可以1s内跑出结果