1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #define MAXM 110  6 #define MAXN 50000  7 #define EPS 1e-8  8 #define INF 0x7FFFFFFF  9 using namespace std; 10 int n, m, k, size; 11 int L[MAXN], R[MAXN], U[MAXN], D[MAXN], C[MAXN]; 12 int H[MAXN], S[MAXN]; 13 bool vis[MAXM]; 14 struct Point { 15     int x, y; 16 }; 17 Point city[MAXM], radar[MAXM]; 18 inline int dbcmp(double x, double y) { 19     if (fabs(x - y) < EPS) 20         return 0; 21     return x > y ? 1 : -1; 22 } 23 double DIS(int i, int j) { 24     double x, y; 25     x = city[i].x - radar[j].x; 26     y = city[i].y - radar[j].y; 27     return x * x + y * y; 28 } 29 void Init() { 30     int i; 31     for (i = 0; i <= m; i++) 32         H[i] = -1; 33     for (i = 0; i <= n; i++) { 34         R[i] = i + 1; 35         L[i + 1] = i; 36         U[i] = D[i] = i; 37         S[i] = 0; 38     } 39     R[n] = 0; 40     size = n + 1; 41 } 42 void Link(int r, int c) { 43     D[size] = D[c]; 44     U[size] = c; 45     U[D[c]] = size; 46     D[c] = size; 47     if (H[r] < 0) 48         H[r] = L[size] = R[size] = size; 49     else { 50         L[size] = H[r]; 51         R[size] = R[H[r]]; 52         L[R[H[r]]] = size; 53         R[H[r]] = size; 54     } 55     S[c]++; 56     C[size++] = c; 57 } 58 int A() { 59     int i, j, k, res; 60     memset(vis, false, sizeof(vis)); 61     for (res = 0, i = R[0]; i; i = R[i]) { 62         if (vis[i]) 63             continue; 64         res++; 65         for (j = D[i]; j != i; j = D[j]) { 66             for (k = R[j]; k != j; k = R[k]) 67                 vis[C[k]] = true; 68         } 69     } 70     return res; 71 } 72 void Remove(int c) { 73     int i; 74     for (i = D[c]; i != c; i = D[i]) { 75         L[R[i]] = L[i]; 76         R[L[i]] = R[i]; 77     } 78 } 79 void Resume(int c) { 80     int i; 81     for (i = D[c]; i != c; i = D[i]) 82         L[R[i]] = R[L[i]] = i; 83 } 84 bool Dance(int now) { 85     if (R[0] == 0) 86         return true; 87     else if (now + A() <= k) { 88         int i, j, temp, c; 89         for (temp = INF,i = R[0]; i; i = R[i]) { 90             if (temp > S[i]) { 91                 temp = S[i]; 92                 c = i; 93             } 94         } 95         for (i = D[c]; i != c; i = D[i]) { 96             Remove(i); 97             for (j = R[i]; j != i; j = R[j]) 98                 Remove(j); 99             if (Dance(now + 1))100                 return true;101             for (j = L[i]; j != i; j = L[j])102                 Resume(j);103             Resume(i);104         }105     }106     return false;107 }108 bool OK(double mid) {109     int i, j;110     Init();111     mid *= mid;112     for (i = 1; i <= n; i++) {113         for (j = 1; j <= m; j++) {114             if (dbcmp(DIS(i, j), mid) <= 0)115                 Link(j, i);116         }117     }118     return Dance(0);119 }120 int main() {121     int T;122     int i;123     double low, high, mid;124     scanf("%d", &T);125     while (T--) {126         scanf("%d%d%d", &n, &m, &k);127         for (i = 1; i <= n; i++)128             scanf("%d%d", &city[i].x, &city[i].y);129         for (i = 1; i <= m; i++)130             scanf("%d%d", &radar[i].x, &radar[i].y);131         for (low = 0, high = 1e5; dbcmp(low, high) < 0;) {132             mid = (low + high) / 2;133             if (OK(mid))134                 high = mid;135             else136                 low = mid;137         }138         printf("%.6lf\n", high);139     }140     return 0;141 }