// Solution to: Easter Eggs // By: Raymond van Bommel // Wrong answer by greedily removing vertices with most neighbours #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]; bool adj[2*MaxN][2*MaxN]; int degree[2*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]) ); } bool poss(double D) { // Check if N eggs can be put, such that the distance between blue and red is at least D. for (int i = 0; i < B+R; i++) { // Begin initialisation degree[i] = 0; for (int j = 0; j < B+R; j++) adj[i][j] = false; } for (int i = 0; i < B; i++) for (int j = 0; j < R; j++) if (distance(i,j) < D) { adj[i][j+B] = true; adj[j+B][i] = true; degree[i]++; degree[j+B]++; } priority_queue < pair > q; for (int i = 0; i < B+R; i++) q.push(make_pair(degree[i], i)); // End initialisation int removed = 0; while (removed < B+R-N) { // Repeatedly look for the vertex with most neighbours pair p = q.top(); q.pop(); if (degree[p.second] != p.first) { // If degree has changed, do not consider and put in the queue again. q.push(make_pair(degree[p.second], p.second)); } else { removed++; // Remove the vertex, all adjacency relations, and decrease the degrees of the neighbours. int i = p.second; for (int j = 0; j < B+R; j++) { if (adj[i][j]) { degree[j]--; adj[i][j] = adj[j][i] = false; } } } } for (int i = 0; i < B+R; i++) for (int j = 0; j < B+R; j++) { // Check if the graph has any edges left, if so, return false. if ( (i != j) && (adj[i][j]) ) { return false; } } // Otherwise return 0. return true; } 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; }