No.2955 Pizza Delivery Plan
Problem Statement
binap works part-time at a pizza shop. Now, $N$ orders have come in at the same time. The $i$-th order ( $1\leq i \leq N$ ) asks for $1$ pizza to be delivered to the house at coordinates $(x_i, y_i)$.
The pizza shop is located at the origin $O(0,0)$ and always has an unlimited stock of pizzas.
binap picks up pizzas at the pizza shop and fulfills the orders, but he can carry at most $K$ pizzas at a time. By stopping by the pizza shop again, he can receive pizzas so that he has $K$ pizzas in hand.
Find the minimum time it takes for binap to depart the pizza shop with $K$ pizzas, complete all the orders, and return to the pizza shop.
The time required to move from coordinates $(x_s,y_s)$ to coordinates $(x_t, y_t)$ is $\sqrt{(x_t-x_s)^2 + (y_t-y_s)^2}$, and the time required to hand over or receive pizzas can be ignored.
Constraints
$1\leq K \leq N \leq 14$
$-10^9\leq x_i, y_i \leq 10^9$ ( $1\leq i \leq N$ )
$i \neq j \iff (x_i,y_i) \neq (x_j, y_j)$
$(x_i,y_i) \neq (0, 0)$ ( $1\leq i \leq N$)
All input values are integers.
Input
$N$ $K$ $x_1$ $y_1$ $x_2$ $y_2$ $\vdots$ $x_N$ $y_N$
Output
Output the answer. Your answer is considered correct if its absolute or relative error from the expected solution is at most $10^{-6}$.
Sample
Sample 1
Input
3 2 1 0 0 1 -2 -2
Output
9.07106781187
Here is one example of a shortest route.
- Move from the pizza shop to house $1$. This takes time $1$, and the number of pizzas in hand decreases from $2$ to $1$.
- Move from house $1$ to house $2$. This takes time $\sqrt 2$, and the number of pizzas in hand decreases from $1$ to $0$.
- Move from house $2$ to the pizza shop. This takes time $1$, and the number of pizzas in hand increases from $0$ to $2$.
- Move from the pizza shop to house $3$. This takes time $2\sqrt 2$, and the number of pizzas in hand decreases from $2$ to $1$.
- Move from house $3$ to the pizza shop. This takes time $2\sqrt 2$.
By delivering along this route, he can finish all the orders and return to the pizza shop. The total time taken is $2 + 5\sqrt 2$, and it is impossible to deliver in less time than this.
Sample 2
Input
3 3 1 0 0 1 -2 -2
Output
8.84819196258
Sample 3
Input
5 3 -1 -2 1 1 5 2 -3 2 -3 1
Output
21.3696545235
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
hamamu