← 返回题目列表

AtCoder · abc157_f

F. 烤肉优化问题

中文机器翻译题面 查看原题

分数: 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