烤肉优化问题

题目描述

高桥君要在二维平面上的烤架上烤 $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}$ 时,判定为正确。

样例

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

2.4

将热源放在 $(-0.2, 0)$ 时,到 $2.4$ 秒为止第 $1, 2, 3$ 块肉能烤熟。这是最优的热源放置方式。

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

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$