/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
高橋君は二次元平面である網の上で N 枚の肉を焼こうとしています。 i 枚目の肉の位置は \left(x_i, y_i\right)であり、火の通りにくさは c_i です。
高橋君は熱源を 1 つ持っています。熱源を位置 \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)に置くと、 2.4 秒後までに 1, 2, 3 枚目の肉が焼けます。これが最適な熱源の置き方です。
入力例 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
Score : 600 points
Problem Statement
Takahashi wants to grill N pieces of meat on a grilling net, which can be seen as a two-dimensional plane. The coordinates of the i-th piece of meat are \left(x_i, y_i\right), and its hardness is c_i.
Takahashi can use one heat source to grill the meat. If he puts the heat source at coordinates \left(X, Y\right), where X and Y are real numbers, the i-th piece of meat will be ready to eat in c_i \times \sqrt{\left(X - x_i\right)^2 + \left(Y-y_i\right)^2} seconds.
Takahashi wants to eat K pieces of meat. Find the time required to have K or more pieces of meat ready if he put the heat source to minimize this time.
Constraints
- All values in input are integers.
- 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
Input
Input is given from Standard Input in the following format:
N K x_1 y_1 c_1 \vdots x_N y_N c_N
Output
Print the answer.
It will be considered correct if its absolute or relative error from our answer is at most 10^{-6}.
Sample Input 1
4 3 -1 0 3 0 0 3 1 0 2 1 1 40
Sample Output 1
2.4
If we put the heat source at \left(-0.2, 0\right), the 1-st, 2-nd, and 3-rd pieces of meat will be ready to eat within 2.4 seconds. This is the optimal place to put the heat source.
Sample Input 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
Sample Output 2
7411.2252