1365 - Gift
Time Limit : 20 Second
Memory Limit : 256 MB
Submission: 2
Solved: 1
- Description
- As a person who regularly participated in ACM contest, lvyun often have the opportunity to travel round the country. Every time, when he came back from the holding place, he will prepare a gift for each friend. This time he arrived in Beijing. Beijing is such a prosperous city that he want to bring the whole city back to Wuhan. So this time he wants to prepare a different gift for each friend, according to the different interest.
Now, the problem is, Lvyun has N friends, and he needs to buy N different gifts which sold in different places in Beijing. To carry so many of gifts, he prepared K boxes. Each box can contain
gifts at most, and when he bought a gift, he can place the gift to any one of the K boxes, except the full one. However, the gift bought last can only places on the top of gifts pile bought before. When he back to Wuhan, he also need to deliver the N gifts to his friends. And it also should be note, that only if the above gifts has been delivered out, the below one can be delivered out. Because of the gifts sold in different place in Beijing and Lvyun’s friends live in different place in Wuhan, Lvyun wants to know the best scheme to buy and deliver these gifts. The best scheme is the one with the minimum sum of tour distance in Beijing and Wuhan. Lvyun always start from (0, 0), where he live in, in Beijing (Wuhan) and buy (deliver) gift one by one, and then came back to (0, 0).
This is an example showing below, he has 8 friends, the corresponding label is 1 to 8, and the label of the gifts for each friend is also 1 to 8. Friend 1 loves gift 1, friend 8 loves gift 8. And he has 3 boxes, which can contain gifts at most. Just as figures show below, figure (a) show the sold places of 8 gifts in Beijing, and the black round point is the hotel Lvyun live in. figure (c) show the places of 8 friends in Wuhan, also the black round point is the place Lvyun live in. The route show in (a) and (c) is one of the best tour scheme. Figure (b) gives out the packing solution of gifts in the boxes for the tour scheme.
- Input
- The input will contain multiple test cases. For each case, the first line is two integer N (N ≤12) and K(K≤N), N is the number of friends, K is the number of boxes. The next 2 * N line, each line with one pair of numbers, will describe the coordinates of N gifts in Beijing and N friends in Wuhan. Please note that Lvyun will always start from (0, 0), both in Beijing or Wuhan.
- Output
- For each test case, just output the minimum sum of tour distance in Beijing and Wuhan. Round the numbers in the output to 3 digits after decimal point.
- sample input
-
4 2 -10.0 10.0 -10.0 -10.0 10.0 -10.0 10.0 10.0 -10.0 10.0 -5.0 -5.0 5.0 -5.0 10.0 10.0
- sample output
-
154.049
- hint
- source
- 中国地质大学(武汉)第七届ACM程序设计大赛暨华中地区部属高校ACM邀请赛