Gopher Strategy

Agent Cooper: “Look at that! Ducks... on the lake!” Harley Peyton, "Twin Peaks." Gophers like to feed in the field, but they always have to look out for hawks that might hunt them. A group of gophers have decided to get more organized and need your help developing an escape strategy in case of a hawk attack. Given the coordinates of m gophers and n holes in the field, what is the minimum time required for each gopher to reach a hole (at most one gopher per hole)? Every gopher runs in a straight line at a speed of 1 unit per second, and the group can tolerate the loss of at most k gophers. (Gophers are lost when they do not have enough time to reach an empty hole.) Input The first line of input gives the number of cases, N. N test cases follow. Each one starts with a line containing the integers m, n and k (0 ≤ m,n ≤ 50,0 ≤ k ≤ m). The next m lines will give the x,y-coordinates of the gophers. The n lines after that will give the coordinates of the holes. Output For each test case, output the line ‘Case #x:’, where x is the number of the test case. Then print the minimum number of seconds required for at least m − k gophers to reach a hole, rounded to 3 decimal places. Every answer will obey the formula |ans∗103 −⌊ans∗103⌋−0.5|>10−2 Print ‘Too bad.’ if there is no solution. Print an empty line after each test case. Sample Input 4 331 00 10 20 01 11 2 1.5 331 01 12 21 10 11 20 330 01 12

2/2 21 10 11 20 100 100.0 200.5 Sample Output Case #1: 1.000 Case #2: 1.000 Case #3: 1.414 Case #4: Too bad.