AT_abc157_f [ABC157F] Yakiniku Optimization Problem

题目描述

高桥君打算在一个二维平面上的网格上烤 $N$ 块肉。第 $i$ 块肉的位置为 $(x_i, y_i)$，其“难烤程度”为 $c_i$。

高桥君有一个热源。如果将热源放在位置 $(X, Y)$（$X, Y$ 为实数），那么第 $i$ 块肉烤熟所需的时间为 $c_i \times \sqrt{(X - x_i)^2 + (Y - y_i)^2}$ 秒。

高桥君想吃 $K$ 块肉。他会选择一种热源的放置方式，使得至少有 $K$ 块肉能在最短时间内烤熟。请你求出这个最短所需时间。

输入格式

输入以如下格式从标准输入读入。

$N$ $K$
$x_1$ $y_1$ $c_1$
$\vdots$
$x_N$ $y_N$ $c_N$

输出格式

请输出答案。

如果你的输出与标准答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。

输入输出样例 #1

输入 #1

4 3
-1 0 3
0 0 3
1 0 2
1 1 40

输出 #1

2.4

输入输出样例 #2

输入 #2

10 5
-879 981 26
890 -406 81
512 859 97
362 -955 25
128 553 17
-885 763 2
449 310 57
-656 -204 11
-270 76 40
184 170 16

输出 #2

7411.2252

说明/提示

限制条件

• 所有输入均为整数。
• $1 \leq N \leq 60$
• $1 \leq K \leq N$
• $-1000 \leq x_i, y_i \leq 1000$
• $(x_i, y_i) \neq (x_j, y_j)\ (i \neq j)$
• $1 \leq c_i \leq 100$

样例解释 1

如果将热源放在 $(-0.2, 0)$，那么在 $2.4$ 秒内，第 $1, 2, 3$ 块肉都能烤熟。这是最优的热源放置方式。

由 ChatGPT 4.1 翻译