// // Solution to problem Easter Eggs // By Mees de Vries // // Expected judgment: ACCEPTED // // Binary search + matching, uses Koenig's theorem for finding maximal // independent set by finding a maximal matching in a biparite graph. #include #include #include #include #include using namespace std; vector vis; vector match; double mid; int N, B, R; vector x, y; int aug(int l) { if(vis[l]) return 0; vis[l] = 1; for(int r = B; r < B + R; r++) { if(sqrt((x[l]-x[r])*(x[l] - x[r]) + (y[l] - y[r])*(y[l]-y[r])) < mid) { if(match[r] == -1 || aug(match[r])) { match[r] = l; return 1; } } } return 0; } int main() { cin >> N >> B >> R; x = vector(B + R), y = vector(B + R); double lo = 0, hi = 0; for(int i = 0; i < B + R; i++) { cin >> x[i] >> y[i]; hi = max(hi, 2*sqrt(x[i]*x[i] + y[i]*y[i])); } while(hi - lo > .00000001) { mid = (hi + lo)/2; int MCBM = 0; match = vector(B + R,-1); for(int l = 0; l < B; l++) { vis = vector(B + R,0); MCBM += aug(l); } if(MCBM + N <= B + R) { lo = mid; } else { hi = mid; } } printf("%.8lf\n",hi); return 0; }