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 \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 翻译