Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM-ICPC竞赛训练》暑期课面向全球招生。容量有限,报名从速!
Language:
Meadow
Time Limit: 1000MSMemory Limit: 30000K
Total Submissions: 531Accepted: 97

Description

As you have probably guessed, we are talking about an ordinary meadow with lot of flowers scattered all around it. Flying between them, landing on them and taking off from them are numerous industrious bees, collecting raw material known as pollen used to produce honey in their hives. Since lives and prosperity of the bee community depends heavily on it, every flower needs to be visited to collect as much pollen as possible.

Maya is the bee who has to make a scheduling list according to which the bees will visit all the flowers on the meadow. A scheduling list consists of several sets of flowers (their positions, actually). Each bee is given one set and it has to visit all the flowers from it in an arbitrary order. Each flower can be visited arbitrary many times. The weight of a sequence of flowers is the largest distance between two successive flowers in the sequence. The weight of a set of flowers is the minimal weight of all sequences of flowers from the set. A bee with given set of flowers will always plan its flight according to the sequence of all flowers from the set with minimal weight. The weight of a scheduling list is the maximal weight of all sets in the scheduling list.

Write a program that will help Maya to find a scheduling list with the lowest weight.

Input

The first line of the input consists of two natural numbers F and B; 1 <= F <= 2000, 1 <= B <= F, F is the number of flowers in the meadow and B is the number of bees available for collecting pollen.

Each of the next C lines contains two natural numbers X and Y, 1 <= X,Y <= 10000, the coordinates of a flower.

Output

The first and only line of the output file should contain the minimal possible weight of a scheduling list for the data given in the input file as described above. The result should be rounded to two decimal places.

Sample Input

3 2
1 1
2 3
3 2

Sample Output

1.41

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator