分数: 600 点
问题陈述
高桥想要烧烤 N 烤网上的肉块,可以看作是一个二维平面。的坐标 i第一块肉是 \left(x_i, y_i\right),及其 硬度 is c_i.
高桥可以使用一个热源来烤肉。如果他把热源放在坐标上 \left(X, Y\right),其中 X 和 Y 是实数, i- 第一块肉将可以在 c_i \times \sqrt{\left(X - x_i\right)^2 + \left(Y-y_i\right)^2} 秒。
高桥想吃东西 K 肉块。找到需要的时间 K 如果准备好或多块肉,他就把热源尽量减少这个时间。
约束
- 输入中的所有值都是整数。
- 1 \leq N \leq 60
- 1 \leq K \leq N
- -1000 \leq x_i , y_i \leq 1000
- \left(x_i, y_i\right) \neq \left(x_j, y_j\right) \left(i \neq j \right)
- 1 \leq c_i \leq 100
输入
输入由标准输入按以下格式给出:
N K x_1 y_1 c_1 \vdots x_N y_N c_N
输出
打印答案。
如果我们的答案的绝对或相对误差最多为,则被认为是正确的 10^{-6}.
示例输入 1
4 3 -1 0 3 0 0 3 1 0 2 1 1 40
示例输出 1
2.4
如果我们将热源放在 \left(-0.2, 0\right), 1-st, 2-nd,和 3-rd 块肉将在 内准备好食用 2.4 秒。这是放置热源的最佳位置。
示例输入 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