import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class harry_greedy_node_removal { static boolean[][] adj; // I opt for the "less-than-optimal" O(N^3) (instead of O(VE)). static int[] prev; static int R, B, totaldegree; static int[] degree; static boolean[] removed; public static void main(String[] args) { int[] xpos, ypos; int target; // Input reading. Scanner sc = new Scanner(System.in); target = sc.nextInt(); B = sc.nextInt(); R = sc.nextInt(); // I swapped R and B. Sorry. xpos = new int[R + B]; ypos = new int[R + B]; for(int i = 0; i < B; i++) { xpos[i + R] = sc.nextInt(); ypos[i + R] = sc.nextInt(); assert(xpos[i + R] <= 10000 && xpos[i + R] >= -10000 && ypos[i + R] <= 10000 && ypos[i + R] >= -10000); } for(int i = 0; i < R; i++) { xpos[i] = sc.nextInt(); ypos[i] = sc.nextInt(); assert(xpos[i] <= 10000 && xpos[i] >= -10000 && ypos[i] <= 10000 && ypos[i] >= -10000); } degree = new int[R + B]; totaldegree = 0; removed = new boolean[R + B]; double minDist = 0, maxDist = 1000000; double precision = Math.pow(10.0, -9); while(maxDist - minDist > precision) { // Reset whatever is necessary. adj = new boolean[R][B]; double dist = (minDist + maxDist) / 2; degree = new int[R + B]; removed = new boolean[R + B]; totaldegree = 0; // Build the graph. for(int i = 0; i < R; i++) for(int j = R; j < R + B; j++) { int xdist = xpos[i] - xpos[j], ydist = ypos[i] - ypos[j]; if(xdist * xdist + ydist * ydist < dist * dist) { adj[i][j - R] = true; degree[i]++; degree[j]++; totaldegree++; } } // Iteratively remove the node with the highest degree to find the maximum number of nodes "left", i.e. the amount of eggs you can hide. This does not work. int left = R + B; while(totaldegree != 0) { int maxdegree = -1; int index = -1; for(int i = 0; i < R + B; i++) { if(degree[i] > maxdegree && !removed[i]) { maxdegree = degree[i]; index = i; } } totaldegree -= degree[index]; degree[index] = 0; if(index < R) { for(int j = 0; j < B; j++) if(adj[index][j]) degree[j + R]--; } else for(int i = 0; i < R; i++) if(adj[i][index - R]) degree[i]--; left--; assert(totaldegree >= 0); } if(left >= target) // We can hide enough eggs, so we should increase the minimal distance. minDist = dist; else maxDist = dist; } System.out.println((minDist + maxDist) / 2); } }