Crop circles
Time Limit: 10000/6000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 3 Accepted Submission(s): 0
Problem Description
Is there really a monster living in Loch Ness?
Did the lost city of Atlantis ever exist?
Are UFOs tricks of the light, or actually vehicles from outer space?
Who is responsible for the strange patterns called crop circles——clever hoaxers or alien beings?
As we can see, there are so many mysterious places, creatures and events in the world which puzzled people for centuries. In this problem, we won’t go through all that puzzles. Which we are interested in is this one -- crop circles.
You have probably seen pictures of crop circles. (i.e. see above) They are circular patterns which mysteriously appear in fields of crop, such as wheat and barley. For research, we model these patterns as N circles in the plane and number them with 1, 2, …, N. Each of them has its center (Xi, Yi), radius Ri and an importance value Vi which is evaluated by the scientists.
After our observation, we found that there aren’t any two circles touch each other in the crop circles. But it’s possible that a circle is completely within another one. When we are in a certain circle, we should pass through its borderline once in order to get out from it.
For two distinct circles A and B, if one can go to B from A without passing through more than K borderlines, we say that A and B are connected. Here comes the problem: For all connected cycle pairs (A, B), what’s the maximum difference of the importance value between them? The difference of the importance value between A and B can be defined as |VA – VB|.
For example, look at the picture below. For K = 3, the optimal solution is to select the circle 1 and 3 which make the difference of importance value 220. And there are 3 borderlines between circle 1 and 3.
|V5 – V1| = 300, which is larger than 220, but circle 5 and circle 1 are not connected. There’re 4 borderlines between them, so we won’t consider these kinds of pairs.
Did the lost city of Atlantis ever exist?
Are UFOs tricks of the light, or actually vehicles from outer space?
Who is responsible for the strange patterns called crop circles——clever hoaxers or alien beings?
As we can see, there are so many mysterious places, creatures and events in the world which puzzled people for centuries. In this problem, we won’t go through all that puzzles. Which we are interested in is this one -- crop circles.
You have probably seen pictures of crop circles. (i.e. see above) They are circular patterns which mysteriously appear in fields of crop, such as wheat and barley. For research, we model these patterns as N circles in the plane and number them with 1, 2, …, N. Each of them has its center (Xi, Yi), radius Ri and an importance value Vi which is evaluated by the scientists.
After our observation, we found that there aren’t any two circles touch each other in the crop circles. But it’s possible that a circle is completely within another one. When we are in a certain circle, we should pass through its borderline once in order to get out from it.
For two distinct circles A and B, if one can go to B from A without passing through more than K borderlines, we say that A and B are connected. Here comes the problem: For all connected cycle pairs (A, B), what’s the maximum difference of the importance value between them? The difference of the importance value between A and B can be defined as |VA – VB|.
For example, look at the picture below. For K = 3, the optimal solution is to select the circle 1 and 3 which make the difference of importance value 220. And there are 3 borderlines between circle 1 and 3.
|V5 – V1| = 300, which is larger than 220, but circle 5 and circle 1 are not connected. There’re 4 borderlines between them, so we won’t consider these kinds of pairs.
Input
The first line of input gives the number of cases T <= 20. T test cases follow.
The first line of each case contains two integers N, K as described above. (1 < N < 50001, 1 < K < 101).
Next follow N lines, each contains four integers Xi, Yi, Ri, Vi, separated by spaces. The i-th line specifying the information of the i-th circle, where (Xi, Yi) are the coordinates of the center, Ri specifies the radius and Vi is the importance value.
(0 < Ri <= 2 * 10^8, -10^9 < Xi, Yi, Vi < 10^9)
The first line of each case contains two integers N, K as described above. (1 < N < 50001, 1 < K < 101).
Next follow N lines, each contains four integers Xi, Yi, Ri, Vi, separated by spaces. The i-th line specifying the information of the i-th circle, where (Xi, Yi) are the coordinates of the center, Ri specifies the radius and Vi is the importance value.
(0 < Ri <= 2 * 10^8, -10^9 < Xi, Yi, Vi < 10^9)
Output
For each test case you should output a single line containing "Case X: Y" (quotes for clarity) where X is the number of the test case (starting at 1) and Y is the maximum difference of importance value between two connected circles.
Sample Input
2 5 3 10 10 1 -200 0 0 8 10 -2 2 2 20 3 -3 3 2 3 -3 1 100 3 2 -200 0 1 0 0 0 100 2 200 0 1 10
Sample Output
Case 1: 220 Case 2: 10