I |
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 coordinate 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.
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).
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 |
Output for Sample Input |
2 |
Case 1: 0.500 |
Problem Setter: Shamim Hafiz, Special Thanks: Tanaeem M Moosa, Jane Alam Jan