// Solution to: Easter Eggs // By: Raymond van Bommel #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define MaxN 250 int N, B, R; double Bx[MaxN], By[MaxN], Rx[MaxN], Ry[MaxN]; double distance(int i, int j) { return sqrt( (Bx[i] - Rx[j])*(Bx[i] - Rx[j]) + (By[i] - Ry[j])*(By[i] - Ry[j]) ); } // Begin maximum matching code // Source of matching code: https://sites.google.com/site/indy256/algo_cpp/hopcroft_karp. const int MAXN1 = MaxN; const int MAXN2 = MaxN; const int MAXM = MaxN*MaxN; int n1, n2, edges, last[MAXN1], previ[MAXM], head[MAXM]; int matching[MAXN2], dist[MAXN1], Q[MAXN1]; bool used[MAXN1], vis[MAXN1]; void init(int _n1, int _n2) { n1 = _n1; n2 = _n2; edges = 0; fill(last, last + n1, -1); } void addEdge(int u, int v) { head[edges] = v; previ[edges] = last[u]; last[u] = edges++; } void bfs() { fill(dist, dist + n1, -1); int sizeQ = 0; for (int u = 0; u < n1; ++u) { if (!used[u]) { Q[sizeQ++] = u; dist[u] = 0; } } for (int i = 0; i < sizeQ; i++) { int u1 = Q[i]; for (int e = last[u1]; e >= 0; e = previ[e]) { int u2 = matching[head[e]]; if (u2 >= 0 && dist[u2] < 0) { dist[u2] = dist[u1] + 1; Q[sizeQ++] = u2; } } } } bool dfs(int u1) { vis[u1] = true; for (int e = last[u1]; e >= 0; e = previ[e]) { int v = head[e]; int u2 = matching[v]; if (u2 < 0 || (!vis[u2]) && (dist[u2] == dist[u1] + 1) && (dfs(u2))) { matching[v] = u1; used[u1] = true; return true; } } return false; } int maxMatching() { fill(used, used + n1, false); fill(matching, matching + n2, -1); for (int res = 0;;) { bfs(); fill(vis, vis + n1, false); int f = 0; for (int u = 0; u < n1; ++u) if (!used[u] && dfs(u)) ++f; if (!f) return res; res += f; } } // End maximum matching code bool poss(double D) { // Check if N eggs can be put, such that the distance between blue and red is at least D. init(B,R); for (int i = 0; i < B; i++) for (int j = 0; j < R; j++) if (distance(i,j) < D) addEdge(i,j); if (B+R - maxMatching() >= N) return true; else return false; } int main () { cin >> N >> B >> R; assert(N <= 250); assert(B < N); assert(R < N); for (int i = 0; i < B; i++) { cin >> Bx[i] >> By[i]; assert(abs(Bx[i]) <= 10000); assert(abs(By[i]) <= 10000); } for (int j = 0; j < R; j++) { cin >> Rx[j] >> Ry[j]; assert(abs(Rx[j]) <= 10000); assert(abs(Ry[j]) <= 10000); } // Binary search the minimal distance between blue and red egg. double hi = sqrt(2.0)*2000000.1; double lo = 0.0; while (hi - lo > 1E-7) { double mid = (hi+lo)/2.0; (poss(mid) ? lo : hi) = mid; } cout.precision(6); cout << fixed << hi << '\n'; return 0; }