Yakiniku Optimization Problem

题目描述

Takahashi 想在一个可以看作二维平面的烤网上烤 $N$ 块肉。第 $i$ 块肉的坐标是 $\left(x_i, y_i\right)$，它的 硬度 为 $c_i$。 Takahashi 可以使用一个热源来烤肉。如果他把热源放在坐标 $\left(X, Y\right)$，其中 $X$ 和 $Y$ 为实数，第 $i$ 块肉将在 $c_i \times \sqrt{\left(X - x_i\right)^2 + \left(Y-y_i\right)^2}$ 秒后熟。 Takahashi 想吃 $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

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$ $\left(x_i, y_i\right) \neq \left(x_j, y_j\right) \left(i \neq j \right)$ $1 \leq c_i \leq 100$如果我们把热源放在 $\left(-0.2, 0\right)$，第 $1$、$2$、$3$ 块肉将在 $2.4$ 秒内熟。这是放置热源的最优位置。

标签: AtCoder|abc157F

来源

AtCoder|abc157F