問題一覧 > 通常問題

No.2955 Pizza Delivery Plan

レベル : / AI推定難易度 : 1700 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が $10^{-6}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : (AC するまで非表示) / 解いたユーザー数 82
作問者 : 👑 binap / テスター : 👑 p-adic 👑 hamamu
お気に入りにしたユーザー ProblemId : 10974 / 自分の提出
問題文最終更新日: 2024-11-02 20:01:29
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 452 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。