Collision of Bacteria

An experiment is being conducted to find out how different colonies of bacteria behave when they collide with each other. The individual colonies are placed on a large dish and the dish can be modeled in a 2D plane. Initially, each colony occupies a rectangular area (sides parallel to axis) and the sizes of these colonies grow with time. The growth of the colonies occurs in the following manner:

1. The x and y coordinate of the lower-left corner decrease.
2. The x coordinate of lower-right corner increases and the y coor- dinate decreases.
3. The x and y coordinate of upper-right corner increase.
4. The x coordinate of upper-left corner decreases and the y coordinate increases. All the increments/decrements mentioned above occur at a constant rate r with respect to time. In this problem, you have to determine the smallest unit of time that elapses when there are at least two colonies that are not more than d distance apart. Here the distance refers to the shortest Euclidean distance between the rectangular areas occupied by the colonies. Input The first line of input will contain T (≤ 100) denoting the number of cases. Each case starts with an integer n (2 ≤ n ≤ 50) denoting the number of colonies. Each of the next n lines contains 4 integers x1 y1 x2 y2 (0 ≤ x1,y1,x2,y2 ≤ 10000, x1 < x2, y1 < y2) where (x1,y1) and (x2,y2) denote the lower-left and upper-right corner of the colony respectively. Next line contains two integers, r and d (1 ≤ r,d ≤ 50). Output For each case, print the case number and the desired result rounded to 3 places after the decimal point. If two colonies overlap or just touch each other, they are considered to be zero distance apart. Sample Input 2 2 0011 3041 11 2 0011 0132 11

2/2 Sample Output Case 1: 0.500 Case 2: 0.000