2017-11-21 11:54

Splendid Moment Collector

  • Golang
  • path
  • as
  • lines
  • each

Problem Description
Being a traveler is always an exciting and memorable experience, especially for iSea. He is a crazy Splendid Moment Collector, not only he likes the wonderful scenery very much, what’s more, he wants himself go through the moment at the very time!

Our beautiful country has N scenic spots, which can be treated as some single points with a coordinate (Xi, Yi), and as a clever prophet, iSea knows the splendid moment of each spots Ti, and he must arrive this spot exactly at Ti time if he want to collect this spot’s splendid moment.
iSea has a speed of V, while travelling between spots, obviously he will choose the shortest path: the straight line. In the beginning, he can choose any spot to start his journey, but in the end, he must return the spot he chooses at first.
Perfectionist pushes himself to gather everything all the time, so does iSea. However, life can’t stand by you the whole days. So iSea wonders the maximum number of splendid moments he can collect, and in all of these journeys have the maximum number, he expects to choose the one has the shortest distance.

The first line contains a single integer T, indicating the number of test cases.
Each test case begins with two integers N, V. Their meanings are the same as the description.
Then N lines follow, each line contains three integers Xi, Yi, Ti, their meanings are also mentioned in the description.

Technical Specification

  1. 1 <= T <= 50
  2. 1 <= N <= 100
  3. 1 <= V <= 1000
  4. 1 <= Ti <= 100000
  5. 1 <= Xi, Yi <= 10000

or each test case, output the case number first, then the maximum number of splendid moments iSea can collect, then the minimum distance among all the eligible journeys, rounded to three fractional digits.

Sample Input
2 2
1 1 1
1 3 2
3 2
1 1 1
2 2 2
1 3 2
3 2
1 1 1
2 2 2
1 3 3

Sample Output
Case 1: 2 4.000
Case 2: 2 2.828
Case 3: 3 4.828

  • 点赞
  • 回答
  • 收藏
  • 复制链接分享