No.2955 Pizza Delivery Plan

問題提出提出一覧質問統計解説

問題一覧 > 通常問題

No.2955 Pizza Delivery Plan

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題　絶対誤差または相対誤差が

10^{-6}

以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : / 解いたユーザー数 81
作問者 : 👑

binap / テスター : 👑

p-adic

hamamu

1 ProblemId : 10974 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2024-11-02 20:01:29

問題文

binapくんはピザ屋さんでアルバイトをしています。今 $N$ 件の注文が同時に入りました。 $i$ 件目 ( $1\leq i \leq N$ ) の注文は座標 $(x_i, y_i)$ にある家に $1$ 枚のピザを届けてほしいという内容です。

ピザ屋さんは原点 $O(0,0)$ にあり常に無数のピザがストックされております。

binapくんはピザ屋さんでピザを受け取り注文をこなしていくのですが、ピザは同時に $K$ 枚までしか運ぶことができず、再びピザ屋さんに立ち寄ることで手持ちのピザが $K$ 枚になるように受け取ることができます。

binapくんがピザを $K$ 枚持った状態でピザ屋さんを出発し、すべての注文を完了して再びピザ屋さんに帰ってくるまでの時間を最小値を求めてください。

座標 $(x_s,y_s)$ から座標 $(x_t, y_t)$ まで移動するのにかかる時間は $\sqrt{(x_t-x_s)^2 + (y_t-y_s)^2}$ であり、ピザの受け渡しにかかる時間は無視できるものとします。

制約

$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$ )
入力は全て整数。

入力

 $N$   $K$ 
 $x_1$   $y_1$ 
 $x_2$   $y_2$ 
 $\vdots$ 
 $x_N$   $y_N$

出力

答えを出力してください。想定解との絶対誤差または相対誤差が $10^{-6}$ 以下であれば正解として扱われます。

サンプル

サンプル1

入力

出力

9.07106781187

最短経路の一例を挙げます。

ピザ屋から家 $1$ へ移動。時間 $1$ かかり、手持ちのピザは $2$ 枚から $1$ 枚に減る。
家 $1$ から家 $2$ へ移動。時間 $\sqrt 2$ かかり、手持ちのピザは $1$ 枚から $0$ 枚に減る。
家 $2$ からピザ屋へ移動。時間 $1$ かかり、手持ちのピザは $0$ 枚から $2$ 枚に増える。
ピザ屋から家 $3$ へ移動。時間 $2\sqrt 2$ かかり、手持ちのピザは $2$ 枚から $1$ 枚に減る。
家 $3$ からピザ屋へ移動。時間 $2\sqrt 2$ かかる。

このようなルートで配達することで全ての注文を終えてピザ屋に帰って来れます。かかる時間の合計は $2 + 5\sqrt 2$ であり、これより短い時間で配達することは不可能です。

サンプル2

入力

出力

8.84819196258

サンプル3

入力

出力

21.3696545235

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。

yukicoder