1301 - Dream
Time Limit : 5 Second
Memory Limit : 128 MB
Submission: 272
Solved: 51
- Description
- After the happy and tired birthday, Gaewah fall asleep and have a dream. He found he was drop into a dark space and can’t go out. The god appears, tell him the space have N lighthouses, all of it are off state. If he wants to go out, he must light more lighthouses. But this is a very special space, and no man can walk in it without use special plane. Even the special plane, cannot fly in the dark place. There are two way can move from a lighthouse to other lighthouses. In a lighted lighthouse can teleport to other lighthouses without any time. Another way is from a lighted lighthouse to an off state lighthouse, but first, the off state one must be lighten by the lighthouse that you want start, and the time cost is the distance between two lighthouses.
In the space all the lighthouse are same, and all them are stand in integer coordinate. Give you a integer K, if a lighthouse is lighted and the coordinate is (x, y), another off state lighthouse’s coordinate is (x1, y1), if |x-x1|+|y-y1|<=K then it can be lighten by the lighthouse in (x, y).
At first, the god will give Gaewah a space plane, and help him light the first lighthouse(any lighthouse can be accept), then you should tell Gaewah the maximum number of lighthouse can be lighted, and then the short time cost.
Notice:
1.The time cost from a lighted lighthouse in (x1, y1) to an unlighted lighthouse in (x2, y2) is sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)))
2 An unlighted lighthouse in (x1,y1) can be lighten by a lighted lighthouse if |x-x1|+|y-y1|<=K - Input
- The first line is a integer t, indicate the number of test case.
For each test case, the first line is two integer N and K as described above.(1<=N<=1000 1<=K<2^31)
Next N line, each have two integer Xi, Yi indicate the I-th lighthouse’s coordinate.(-10^8<=Xi,Yi<=10^8). - Output
- For each test case, output two number, the maximum lighthouse can be light(include the first one that god lighted) and the minimum time cost, the time is a floating number with two digits after decimal point.
- sample input
-
1 4 5 2 7 5 4 2 1 3 3
- sample output
-
4 8.60
- hint
- source
- Hust Monthly 09.08.21/Zehua HONG