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:
- The x and y coordinate of the lower-left corner decrease.
- The x coordinate of lower-right corner increases and the y coor-
dinate decreases.
- The x and y coordinate of upper-right corner increase.
- 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