题目详情题解（0）讨论（0）提交记录（0）

AT_abc157_f.[ABC157F] Yakiniku Optimization Problem

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

高桥君打算在一个二维平面上的网格上烤 NN 块肉。第 ii 块肉的位置为 (xi,yi)(x_i, y_i)，其“难烤程度”为 cic_i。

高桥君有一个热源。如果将热源放在位置 (X,Y)(X, Y)（X,YX, Y 为实数），那么第 ii 块肉烤熟所需的时间为 ci×(X−xi)2+(Y−yi)2c_i \times \sqrt{(X - x_i)^2 + (Y - y_i)^2} 秒。

高桥君想吃 KK 块肉。他会选择一种热源的放置方式，使得至少有 KK 块肉能在最短时间内烤熟。请你求出这个最短所需时间。

输入格式

输入以如下格式从标准输入读入。

NN KK
x1x_1 y1y_1 c1c_1
⋮\vdots
xNx_N yNy_N cNc_N

输出格式

请输出答案。

如果你的输出与标准答案的绝对误差或相对误差不超过 10−610^{-6}，则视为正确。

输入输出样例

  • 输入#1

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

    输出#1

    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

说明/提示

限制条件

  • 所有输入均为整数。
  • 1≤N≤601 \leq N \leq 60
  • 1≤K≤N1 \leq K \leq N
  • −1000≤xi,yi≤1000-1000 \leq x_i, y_i \leq 1000
  • (xi,yi)≠(xj,yj) (i≠j)(x_i, y_i) \neq (x_j, y_j)\ (i \neq j)
  • 1≤ci≤1001 \leq c_i \leq 100

样例解释 1

如果将热源放在 (−0.2,0)(-0.2, 0)，那么在 2.42.4 秒内，第 1,2,31, 2, 3 块肉都能烤熟。这是最优的热源放置方式。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页