1 #include
     
        2 #include
      
         3 #include
       
          4 #define MAXM 20  5 #define MAXN 10000  6 #define EPS 1e-8  7 #define INF 0x7FFFFFFF  8 int L[MAXN], R[MAXN], U[MAXN], D[MAXN];  9 int S[MAXN], H[MAXN], C[MAXN], B[MAXN]; 10 double dis[MAXM][MAXM]; 11 bool vis[MAXM]; 12 struct Point { 13     double x, y; 14 }; 15 Point p[MAXM], center[MAXN]; 16 int n, m, size; 17 inline int dbcmp(double x, double y) { 18     if (fabs(x - y) < EPS) 19         return 0; 20     return x > y ? 1 : -1; 21 } 22 inline double DIS(Point a, Point b) { 23     double x, y; 24     x = b.x - a.x; 25     y = b.y - a.y; 26     return x * x + y * y; 27 } 28 void Init() { 29     int i; 30     for (i = 0; i <= n; i++) { 31         R[i] = i + 1; 32         L[i + 1] = i; 33         U[i] = D[i] = i; 34         S[i] = 0; 35     } 36     R[n] = 0; 37     size = n + 1; 38 } 39 void Link(int r, int c) { 40     D[size] = D[c]; 41     U[size] = c; 42     U[D[c]] = size; 43     D[c] = size; 44     if (H[r] < 0) 45         H[r] = L[size] = R[size] = size; 46     else { 47         L[size] = H[r]; 48         R[size] = R[H[r]]; 49         L[R[H[r]]] = size; 50         R[H[r]] = size; 51     } 52     S[c]++; 53     C[size++] = c; 54 } 55 int A() { 56     int i, j, k, res; 57     memset(vis, false, sizeof(vis)); 58     for (res = 0, i = R[0]; i; i = R[i]) { 59         if (vis[i]) 60             continue; 61         res++; 62         for (j = D[i]; j != i; j = D[j]) { 63             for (k = R[j]; k != j; k = R[k]) 64                 vis[C[k]] = true; 65         } 66     } 67     return res; 68 } 69 void Remove(int c) { 70     int i; 71     for (i = D[c]; i != c; i = D[i]) { 72         L[R[i]] = L[i]; 73         R[L[i]] = R[i]; 74     } 75 } 76 void Resume(int c) { 77     int i; 78     for (i = D[c]; i != c; i = D[i]) 79         L[R[i]] = R[L[i]] = i; 80 } 81 bool Dance(int now) { 82     if (now + A() > m) 83         return false; 84     if (R[0] == 0) 85         return true; 86     int i, j, temp, c; 87     for (temp = INF,i = R[0]; i; i = R[i]) { 88         if (temp > S[i]) { 89             temp = S[i]; 90             c = i; 91         } 92     } 93     for (i = D[c]; i != c; i = D[i]) { 94         Remove(i); 95         for (j = R[i]; j != i; j = R[j]) 96             Remove(j); 97         if (Dance(now + 1)) 98             return true; 99         for (j = L[i]; j != i; j = L[j])100             Resume(j);101         Resume(i);102     }103     return false;104 }105 void Center(int i, int j, double r, int &cnt) {106     double x0, y0, x1, y1, d;107     if (dbcmp(dis[i][j], 0) == 0)108         center[cnt++] = p[i];109     else if (dbcmp(dis[i][j], 2 * r) == 0) {110         center[cnt].x = (p[i].x + p[j].x) / 2;111         center[cnt++].y = (p[i].y + p[j].y) / 2;112     } else if (dbcmp(dis[i][j], 2 * r) < 0) {113         x0 = (p[i].x + p[j].x) / 2;114         y0 = (p[i].y + p[j].y) / 2;115         x1 = (p[i].x - p[j].x) / 2;116         y1 = (p[i].y - p[j].y) / 2;117         d = sqrt(r * r - x1 * x1 - y1 * y1) / dis[i][j];118         center[cnt].x = (p[j].y - p[i].y) * d + x0;119         center[cnt++].y = (p[i].x - p[j].x) * d + y0;120         center[cnt].x = (p[i].y - p[j].y) * d + x0;121         center[cnt++].y = (p[j].x - p[i].x) * d + y0;122     }123 }124 bool OK(double r) {125     int i, j, k, cnt;126     Init();127     for (cnt = 0, i = 1; i <= n; i++) {128         for (j = i; j <= n; j++)129             Center(i, j, r, cnt);130     }131     for (r *= r, i = 0; i < cnt; i++) {132         H[i] = -1;133         B[i] = 0;134         for (j = 1; j <= n; j++) {135             B[i] <<= 1;136             if (dbcmp(DIS(center[i], p[j]), r) <= 0)137                 B[i] |= 1;138         }139     }140     for (i = 0; i < cnt; i++) {141         for (j = i + 1; j < cnt; j++) {142             if ((B[i] | B[j]) == B[j])143                 break;144         }145         if (j == cnt) {146             for (k = 0; k < n; k++) {147                 if (B[i] & (1 << k))148                     Link(i, k + 1);149             }150         }151     }152     return Dance(0);153 }154 int main() {155     int T, i, j;156     double low, high, mid;157     scanf("%d", &T);158     while (T--) {159         scanf("%d%d", &n, &m);160         for (i = 1; i <= n; i++)161             scanf("%lf%lf", &p[i].x, &p[i].y);162         for (i = 1; i <= n; i++) {163             dis[i][i] = 0;164             for (j = i + 1; j <= n; j++)165                 dis[i][j] = dis[j][i] = sqrt(DIS(p[i], p[j]));166         }167         for (low = 0, high = 15; dbcmp(low, high) < 0;) {168             mid = (low + high) / 2;169             if (OK(mid))170                 high = mid;171             else172                 low = mid;173         }174         printf("%lf\n", low);175     }176     return 0;177 }