题目描述：

给你n（19）个点， 和一个数字m。让你用m个半径相同的圆取覆盖这n个点，问你半径的最小值是多少。

解题报告：

二分枚举半径，对于每个二分值mid，枚举任意n个点中的两个i和j

求以i，j为圆心，mid为半径的圆的交点的集合。

以这些交点为实际的圆心，记录每个交点为圆心能覆盖n个点中的哪些。

DLX求解最少需要的圆，在m以内的话，符合条件r = mid，否则l = mid

代码如下：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define eps 1e-7
struct pint{double x, y;} jeo[20], inter[500];
int num, t, n, m;
const int max_size = 500 * 20;
const int maxint = 0x3f3f3f3f;
int L[max_size], R[max_size], U[max_size], D[max_size], CH[max_size];
int S[20];
int head, size;
void remove(const int &c) {
    for (int i = D[c]; i != c; i = D[i]) {
        L[R[i]] = L[i], R[L[i]] = R[i];
        --S[CH[i]];
    }
}
void resume(const int &c) {
    for (int i = U[c]; i != c; i = U[i]) {
        ++S[CH[i]];
        L[R[i]] = R[L[i]] = i;
    }
}
int H() {
    int cnt = 0;
    bool cover[500] = {false};
    for (int c = R[head]; c != head; c = R[c])
        if (!cover[c]) {
            cover[c] = true, ++cnt;
            for (int i = D[c]; i != c; i = D[i])
                for (int j = R[i]; j != i; j = R[j])
                    cover[CH[j]] = true;
        }
    return cnt;
}
int ans, ans_cnt;
void dfs(const int &k) {
    if (R[head] == head) {
        ans = min(ans, k);
        return;
    }
    int s(maxint), c;
    for (int t = R[head]; t != head; t = R[t]) {
        if (S[t] < s) s = S[t], c = t;
    }
    for (int i = D[c]; i != c; i = D[i]) {
        remove(i);
        for (int j = R[i]; j != i; j = R[j])
            remove(j);
        if (k + 1 + H() < ans)
            dfs(k + 1);
        for (int j = L[i]; j != i; j = L[j])
            resume(j);
        resume(i);
    }
}
int node(int up, int down, int left, int right) {
    U[size] = up, D[size] = down;
    L[size] = left, R[size] = right;
    D[up] = U[down] = R[left] = L[right] = size;
    return size++;
}

bool G[500][20];
void init(int N, int M) {
    size = 0;
    head = node(0, 0, 0, 0);
    for (int j = 1; j <= M; ++j) {
        node(j, j, L[head], head);
        CH[j] = j, S[j] = 0;
    }
    int u, v;
    for (int u = 1; u <= N; ++u) {
        int row = -1;
        for (int v = 1; v <= M; ++v) {
            if (!G[u][v]) continue;
            if (row == -1) {
                row = node(U[CH[v]], CH[v], size, size);
                CH[row] = v, ++S[v];
            } else {
                int k = node(U[CH[v]], CH[v], L[row], row);
                CH[k] = v, ++S[v];
            }
        }
    }
}
double dist(pint p1,pint p2){
 return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
int intersect_circle_circle(pint c1,double r1,pint c2,double r2){
 return dist(c1,c2)<r1+r2+eps&&dist(c1,c2)>fabs(r1-r2)-eps;
}

pint intersection(pint u1,pint u2,pint v1,pint v2){
 pint ret=u1;
 double t=((u1.x-v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x))
   /((u1.x-u2.x)*(v1.y-v2.y)-(u1.y-u2.y)*(v1.x-v2.x));
 ret.x+=(u2.x-u1.x)*t;
 ret.y+=(u2.y-u1.y)*t;
 return ret;
}
void intersection_line_circle(pint c,double r,pint l1,pint l2,pint& p1,pint& p2){
 pint p=c;
 double t;
 p.x+=l1.y-l2.y;
 p.y+=l2.x-l1.x;
 p=intersection(p,c,l1,l2);
 t=sqrt(r*r-dist(p,c)*dist(p,c))/dist(l1,l2);
 p1.x=p.x+(l2.x-l1.x)*t;
 p1.y=p.y+(l2.y-l1.y)*t;
 p2.x=p.x-(l2.x-l1.x)*t;
 p2.y=p.y-(l2.y-l1.y)*t;
}

//计算圆与圆的交点,保证圆与圆有交点,圆心不重合
void intersection_circle_circle(pint c1,double r1,pint c2,double r2,pint& p1,pint& p2){
 pint u,v;
 double t;
 t=(1+(r1*r1-r2*r2)/dist(c1,c2)/dist(c1,c2))/2;
 u.x=c1.x+(c2.x-c1.x)*t;
 u.y=c1.y+(c2.y-c1.y)*t;
 v.x=u.x+c1.y-c2.y;
 v.y=u.y-c1.x+c2.x;
 intersection_line_circle(c1,r1,u,v,p1,p2);
}
int main()
{
    scanf("%d", &t);
    for(int ca = 1; ca <= t; ca++)
    {
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; i++)
            scanf("%lf%lf", &jeo[i].x, &jeo[i].y);
        printf("Case %d: ", ca);
        if (m >= n) {printf("0.00\n"); continue;}
        double l = 0, r = 10000;
        while(r - l >= eps)
        {
            double mid = (l + r) * 0.5;
            int num = 1;
            for(int i = 1; i <= n; i++)
            {
                inter[num++] = jeo[i];
                for(int j = i + 1; j <= n; j++)
                    if (intersect_circle_circle(jeo[i], mid, jeo[j], mid))
                    {
                        intersection_circle_circle(jeo[i], mid, jeo[j], mid, inter[num], inter[num+1]);
                        num += 2;
                    }
            }
            for(int i = 1; i < num; i++)
                for(int j = 1; j <= n; j++)
                    G[i][j] = (mid - dist(jeo[j], inter[i]) >= -eps);
            init(num - 1, n);
            ans = maxint;
            dfs(1);
            if(ans - 1 <= m) r = mid;
            else l = mid;
        }
        printf("%.2f\n", l);
    }
    return 0;
}