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-----
4 3
-1 0 3
0 0 3
1 0 2
1 1 40

-----Sample Output-----
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.

Difficulty: interview

Starter code:

Solutions:
import sys
from itertools import combinations
from math import sqrt
import numpy as np

read = sys.stdin.read
readline = sys.stdin.readline


def main():
    N, K, *xyc = list(map(int, read().split()))
    x = xyc[::3]
    y = xyc[1::3]
    xy = list(zip(x, y))
    c = xyc[2::3]
    left = 0
    right = 10 ** 6
    delta = 0.1 ** 7
    while right - left > delta:
        mid = (left + right) / 2
        intersections = []
        r = [(mid / i) ** 2 for i in c]
        for i, j in combinations(list(range(N)), 2):
            x1, y1 = xy[i]
            x2, y2 = xy[j]
            X = x2 - x1
            Y = y2 - y1
            XY = X ** 2 + Y ** 2
            r1 = r[i]
            r2 = r[j]

            a = (XY + r1 - r2) / 2
            b = XY * r1 - a ** 2
            if b < delta:
                continue
            b = sqrt(b)
            xi1 = (a * X + Y * b) / XY + x1
            yi1 = (a * Y - X * b) / XY + y1
            xi2 = (a * X - Y * b) / XY + x1
            yi2 = (a * Y + X * b) / XY + y1
            intersections.append((xi1, yi1))
            intersections.append((xi2, yi2))

        intersections.extend(xy)
        intersections = np.array(intersections, np.float)
        cnt = np.zeros(len(intersections), np.int64)

        for (i, j), k in zip(xy, r):
            XY = (intersections[:, 0] - i) ** 2 + (intersections[:, 1] - j) ** 2
            cnt[XY < k + delta] += 1

        if np.any(cnt >= K):
            right = mid
        else:
            left = mid

    print(right)


def __starting_point():
    main()

__starting_point()

from math import hypot

def solve():
    N, K = list(map(int, input().split()))
    xs, ys, cs = [], [], []
    for _ in range(N):
        x, y, c = list(map(int, input().split()))
        xs.append(x)
        ys.append(y)
        cs.append(c)

    EPS = 10**-10
    def isLE(a, b):
        return not (a > b+EPS)

    def getIntersectionLCs(a, b, c, xC, yC, r):
        e = a*xC + b*yC + c
        ab2 = a**2 + b**2
        v = r**2 * ab2 - e**2
        if v < 0:
            return []
        elif v == 0:
            xP = xC + -a*e / ab2
            yP = yC + -b*e / ab2
            return [(xP, yP)]
        else:
            v = v**0.5
            ae, be = a*e, b*e
            av, bv = a*v, b*v
            xP1 = xC + (-ae + bv) / ab2
            yP1 = yC + (-be - av) / ab2
            xP2 = xC + (-ae - bv) / ab2
            yP2 = yC + (-be + av) / ab2
            return [(xP1, yP1), (xP2, yP2)]

    def getIntersectionCCs(x1, y1, r1, x2, y2, r2):
        xC, yC = x2-x1, y2-y1
        c = -(xC**2 + yC**2 + r1**2 - r2**2) / 2
        intCCs = getIntersectionLCs(xC, yC, c, 0, 0, r1)
        intCCs = [(x1 + x, y1 + y) for x, y in intCCs]
        return intCCs

    def countNum(xP, yP, xs, ys, rs, K):
        num = 0
        for i, (x, y, r) in enumerate(zip(xs, ys, rs), start=1):
            dist = hypot(x-xP, y-yP)
            if isLE(dist, r):
                num += 1
            if num >= K:
                return True
            elif num+N-i < K:
                return False
        return num >= K

    def isOK(t):
        rs = [t/c for c in cs]

        for xP, yP in zip(xs, ys):
            if countNum(xP, yP, xs, ys, rs, K):
                return True

        for i in range(N):
            x1, y1, r1 = xs[i], ys[i], rs[i]
            for j in range(i+1, N):
                x2, y2, r2 = xs[j], ys[j], rs[j]
                intCCs = getIntersectionCCs(x1, y1, r1, x2, y2, r2)
                for xP, yP in intCCs:
                    if countNum(xP, yP, xs, ys, rs, K):
                        return True

        return False

    ng, ok = 0, 2*10**5
    while abs(ok-ng) > 10**-7:
        mid = (ng+ok) / 2
        if isOK(mid):
            ok = mid
        else:
            ng = mid

    print(ok)


solve()


from math import hypot
from collections import deque

N, K, *XYC = map(int, open(0).read().split())
XYC = list(zip(*[iter(XYC)] * 3))

Q = deque([(0, 0, 1000.0)])

ans = float("inf")
while Q:
    X, Y, r = Q.popleft()
    if ans * 0.9999995 > sorted(c * hypot(max(abs(X - x) - r, 0), max(abs(Y - y) - r, 0)) for x, y, c in XYC)[K - 1]:
        ans = min(ans, sorted(c * hypot(X - x, Y - y) for x, y, c in XYC)[K - 1])
        r /= 2
        Q += [
            (X + r, Y + r, r),
            (X - r, Y + r, r),
            (X + r, Y - r, r),
            (X - r, Y - r, r),
        ]

print(ans)

def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline
    from math import hypot
    from collections import deque

    N, K = map(int, input().split())
    XYC = [tuple(map(int, input().split())) for _ in range(N)]

    dq = deque([(0, 0, 1000.0)])

    ans = 10**18
    while dq:
        X, Y, r = dq.popleft()
        c_hypot = [c * hypot(max(abs(X - x) - r, 0), max(abs(Y - y) - r, 0)) for x, y, c in XYC]
        c_hypot.sort()
        if ans * 0.9999995 > c_hypot[K-1]:
            c_hypot = [c * hypot(X - x, Y - y) for x, y, c in XYC]
            c_hypot.sort()
            if c_hypot[K-1] < ans:
                ans = c_hypot[K-1]

            r /= 2
            dq += [
                (X + r, Y + r, r),
                (X - r, Y + r, r),
                (X + r, Y - r, r),
                (X - r, Y - r, r),
            ]
    print(ans)

main()

import sys
from itertools import combinations
from math import atan2, cos, sin


def apollonius(p1, c1, p2, c2):
    m1 = p1 + (p2 - p1) * c2 / (c1 + c2)
    m2 = p1 + (p2 - p1) * c2 / (c2 - c1)
    m = (m1 + m2) / 2
    r = abs(m1 - m)
    return m, r


def apollonius_intersections(p1, c1, p2, c2, p3, c3):
    m12, r12 = apollonius(p1, c1, p2, c2)
    m13, r13 = apollonius(p1, c1, p3, c3)
    v = m13 - m12
    d = abs(v)
    if d > r12 + r13 or d < abs(r12 - r13):
        return None, None
    theta = atan2(v.imag, v.real)
    xx = (r12 ** 2 - r13 ** 2 + d ** 2) / (2 * d)
    s = (r12 + r13 + d) / 2
    yy = 2 * (s * (s - r12) * (s - r13) * (s - d)) ** 0.5 / d
    st = sin(theta)
    ct = cos(theta)
    e1 = (xx * ct - yy * st) + (xx * st + yy * ct) * 1j + m12
    e2 = (xx * ct + yy * st) + (xx * st - yy * ct) * 1j + m12

    t1 = abs(e1 - p1) * c1
    t2 = abs(e2 - p1) * c1
    if t1 < t2:
        return e1, t1
    return e2, t2


def get_circumscribed_center(p1, p2, p3):
    A = abs(p2 - p3) ** 2
    B = abs(p3 - p1) ** 2
    C = abs(p1 - p2) ** 2
    T = A * (B + C - A)
    U = B * (C + A - B)
    W = C * (A + B - C)
    # Debug
    try:
        return (T * p1 + U * p2 + W * p3) / (T + U + W)
    except:
        return 0j


def solve(n, k, xyc):
    if k == 1:
        return 0

    xxx = xyc[0::3]
    yyy = xyc[1::3]
    ccc = xyc[2::3]
    beefs = [(i, x + y * 1j, c) for i, (x, y, c) in enumerate(zip(xxx, yyy, ccc))]

    ans = 1e18
    for (i1, p1, c1), (i2, p2, c2) in combinations(beefs, 2):
        # 肉2枚の比重を考慮した等距離点に熱源を置いたときの時間tを算出
        # →t以内に焼ける肉がK以上あれば、その2枚を含む場合の最小時間はt
        px = p1 + (p2 - p1) * (c2 / (c1 + c2))
        t = abs(px - p1) * c1 + 1e-8

        ok = 0
        ng = []
        for i, p, c in beefs:
            if abs(px - p) * c <= t:
                ok += 1
            else:
                ng.append(i)
        if ok >= k:
            ans = min(ans, t)
            continue

        # REが出る。原因はここ以下

        # K枚以上ない場合、範囲外のどれかの肉をギリギリ含めることを考える
        # （重複を防ぐため、j > i2 の肉を調べる）
        # 2点からの比が等しい点の軌跡は、c1==c2なら垂直二等分線、それ以外はアポロニウスの円
        # p1-p2, p2-p3, p3-p1 の3円（または直線）が1点で交わる箇所があるか
        # ある → そこに熱源を置き、時間tを算出、t以内に焼ける肉がK以上あるか調べる
        # ない → 他の2点または3点で考えた方がよい
        for i3 in ng:
            if i3 < i2:
                continue
            _, p3, c3 = beefs[i3]
            if c1 == c2:
                if c2 == c3:
                    e = get_circumscribed_center(p1, p2, p3)
                    t = abs(e - p1) * c1
                else:
                    e, t = apollonius_intersections(p3, c3, p1, c1, p2, c2)
            elif c1 == c3:
                e, t = apollonius_intersections(p2, c2, p1, c1, p3, c3)
            else:
                e, t = apollonius_intersections(p1, c1, p2, c2, p3, c3)

            if e is None:
                continue

            t += 1e-8
            ok2 = 0
            for i, p, c in beefs:
                if abs(e - p) * c <= t:
                    ok2 += 1
            if ok2 >= k:
                ans = min(ans, t)

    return ans


n, k = list(map(int, input().split()))
xyc = list(map(int, sys.stdin.read().split()))
print((solve(n, k, xyc)))


from math import hypot
from collections import deque

N, K, *XYC = map(int, open(0).read().split())
XYC = list(zip(*[iter(XYC)] * 3))

Q = deque([(0, 0, 1000.0)])

ans = float("inf")
while Q:
    X, Y, r = Q.popleft()
    if ans * 0.9999995 > sorted(c * hypot(max(abs(X - x) - r, 0), max(abs(Y - y) - r, 0)) for x, y, c in XYC)[K - 1]:
        ans = min(ans, sorted(c * hypot(X - x, Y - y) for x, y, c in XYC)[K - 1])
        for dx, dy in [(-0.5, -0.5), (-0.5, 0.5), (0.5, -0.5), (0.5, 0.5)]:
            Q.append((X + dx * r, Y + dy * r, r / 2))

print(ans)

# 多くても 3 つがぎりぎり焼ける位置
from math import acos
from cmath import exp
from itertools import combinations
N, K = list(map(int, input().split()))
XYC = []
for _ in range(N):
    x, y, c = list(map(int, input().split()))
    XYC.append((complex(x, y), c))
if K==1:
    print((0))
    return
ans = 1e300
eps = 1e-7
for (p1, c1), (p2, c2) in combinations(XYC, 2):
    p_center = (p1 * c1 + p2 * c2) / (c1 + c2)
    t = abs(p_center-p1) * c1
    k = 0
    for xy, c in XYC:
        if abs(p_center-xy) * c < t + eps:
            k += 1
    if k >= K and t < ans:
        ans = t

def get_center(p1, p2, p3, c1, c2, c3):
    if c1 == c2 == c3:
        t1, t2, t3 = p2-p3, p3-p1, p1-p2
        denom = (t1*p1.conjugate()+t2*p2.conjugate()+t3*p3.conjugate())
        if denom == 0:
            return []
        return [(t1*abs(p1)**2+t2*abs(p2)**2+t3*abs(p3)**2) / denom]
    elif c1 == c3:
        c2, c3 = c3, c2
        p2, p3 = p3, p2
    elif c2 == c3:
        c1, c3 = c3, c1
        p1, p3 = p3, p1
    o1 = (c1*c1*p1-c3*c3*p3)/(c1*c1-c3*c3)
    r1 = (c1*c3*abs(p1-p3))/abs(c1*c1-c3*c3)
    o2 = (c2*c2*p2-c3*c3*p3)/(c2*c2-c3*c3)
    r2 = (c2*c3*abs(p2-p3))/abs(c2*c2-c3*c3)
    l = abs(o1-o2)
    if r1+r2 < l or l+r1<r2 or l+r2<r1:
        return []
    cos_a = (r1*r1+l*l-r2*r2)/(2*r1*l)
    a = acos(cos_a)
    res1 = o1 + (o2-o1) * exp(a*1j) * r1 / l
    res2 = o1 + (o2-o1) * exp(-a*1j) * r1 / l
    return [res1, res2]

for (p1, c1), (p2, c2), (p3, c3) in combinations(XYC, 3):
    p_centers = get_center(p1, p2, p3, c1, c2, c3)
    for p_center in p_centers:
        t = abs(p1 - p_center) * c1
        # print(abs(p1 - p_center) * c1,
        #       abs(p2 - p_center) * c2,
        #       abs(p3 - p_center) * c3)
        k = 0
        for p, c in XYC:
            if abs(p_center - p) * c < t + eps:
                k += 1
        if k >= K and t < ans:
            ans = t

print(ans)


# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
from itertools import combinations

def run():
    N, K = map(int, sysread().split())
    niku = []
    for i in range(N):
        niku.append([i]+list(map(int, sysread().split())))

    high_t = math.sqrt(2000**2 + 2000**2) * 101
    low_t = 0
    current = (high_t + low_t) / 2
    delta = 5e-7
    if K == 1:
        print(0)
        return None

    while high_t - low_t > delta:
        done = False
        c = [(current / ci) ** 2 for _, _, _, ci in niku]
        for i, xi, yi, _ in niku:
            if done:
                break
            K0 = 0
            for k, xk, yk, _ in niku:
                if done:
                    break
                ck = c[k]
                if ((xi - xk) ** 2 + (yi - yk) ** 2) <= ck + delta:
                    K0 += 1
                if K0 >= K:
                    done = True


        for (i, xi, yi, _), (j, xj, yj, _) in combinations(niku, 2):
            if done:
                break
            ci, cj = c[i], c[j]
            xj -= xi
            yj -= yi
            d2 = xj ** 2 + yj ** 2
            d = math.sqrt(d2)

            x = (d2 + ci - cj) / (2 * d)
            e = ci - x ** 2
            if e < 0 or math.sqrt(ci) + math.sqrt(cj) < d:
                continue
            else:
                e = math.sqrt(e)

            vx1, vy1 = xj / d, yj / d
            vx2, vy2 = yj / d, -xj / d

            X1 = vx1 * x + vx2 * e + xi
            X2 = vx1 * x - vx2 * e + xi
            Y1 = vy1 * x + vy2 * e + yi
            Y2 = vy1 * x - vy2 * e + yi

            K1 = 0
            K2 = 0

            for k, xk, yk, _ in niku:
                if done:
                    break
                ck = c[k]
                if ((xk - X1) ** 2 + (yk - Y1) ** 2) <= ck + delta:
                    K1 += 1
                if ((xk - X2) ** 2 + (yk - Y2) ** 2) <= ck + delta:
                    K2 += 1
                if K1 >= K or K2 >= K:
                    done = True


        if done:
            high_t = current
            current = (high_t + low_t) / 2
        else:
            low_t = current
            current = (high_t + low_t) / 2

    print((low_t + high_t) / 2)
    return None

def __starting_point():
    run()
__starting_point()

import math

n, k = map(int, input().split())
x, y, c = zip(*[map(int, input().split()) for _ in range(n)])
que = [(0, 0, 1000)]
res = 1e9
i = 0
while i < len(que):
    px, py, r = que[i]
    i += 1
    lb = [c[j] * math.hypot(max(abs(px - x[j]) - r, 0), max(abs(py - y[j]) - r, 0)) for j in range(n)]
    if res * (1 - 5e-7) > sorted(lb)[k - 1]:
        dis = [c[j] * math.hypot(px - x[j], py - y[j]) for j in range(n)]
        res = min(res, sorted(dis)[k - 1])
        for dx in (-0.5, 0.5):
            for dy in (-0.5, 0.5):
                que.append((px + dx * r, py + dy * r, r / 2))
print(res)

import sys
from itertools import combinations
from math import atan2, cos, sin


def apollonius(p1, c1, p2, c2):
    m1 = p1 + (p2 - p1) * c2 / (c1 + c2)
    m2 = p1 + (p2 - p1) * c2 / (c2 - c1)
    m = (m1 + m2) / 2
    r = abs(m1 - m)
    return m, r


def apollonius_intersections(p1, c1, p2, c2, p3, c3):
    m12, r12 = apollonius(p1, c1, p2, c2)
    m13, r13 = apollonius(p1, c1, p3, c3)
    v = m13 - m12
    d = abs(v)
    if d > r12 + r13 or d < abs(r12 - r13):
        return None, None
    theta = atan2(v.imag, v.real)
    xx = (r12 ** 2 - r13 ** 2 + d ** 2) / (2 * d)
    s = (r12 + r13 + d) / 2
    yy = 2 * (s * (s - r12) * (s - r13) * (s - d)) ** 0.5 / d
    st = sin(theta)
    ct = cos(theta)
    e1 = (xx * ct - yy * st) + (xx * st + yy * ct) * 1j + m12
    e2 = (xx * ct + yy * st) + (xx * st - yy * ct) * 1j + m12

    t1 = abs(e1 - p1) * c1
    t2 = abs(e2 - p1) * c1
    if t1 < t2:
        return e1, t1
    return e2, t2


def get_circumscribed_center(p1, p2, p3):
    A = abs(p2 - p3) ** 2
    B = abs(p3 - p1) ** 2
    C = abs(p1 - p2) ** 2
    T = A * (B + C - A)
    U = B * (C + A - B)
    W = C * (A + B - C)
    try:
        return (T * p1 + U * p2 + W * p3) / (T + U + W)
    except:
        return 0j


def solve(n, k, xyc):
    if k == 1:
        return 0

    xxx = xyc[0::3]
    yyy = xyc[1::3]
    ccc = xyc[2::3]
    beefs = [(i, x + y * 1j, c) for i, (x, y, c) in enumerate(zip(xxx, yyy, ccc))]

    ans = 1e18
    for (i1, p1, c1), (i2, p2, c2) in combinations(beefs, 2):
        # 肉2枚の比重を考慮した等距離点に熱源を置いたときの時間tを算出
        # →t以内に焼ける肉がK以上あれば、その2枚を含む場合の最小時間はt
        px = p1 + (p2 - p1) * (c2 / (c1 + c2))
        t = abs(px - p1) * c1 + 1e-8

        ok = 0
        ng = []
        for i, p, c in beefs:
            if abs(px - p) * c <= t:
                ok += 1
            else:
                ng.append(i)
        if ok >= k:
            ans = min(ans, t)
            continue
        # p1,p2の2点を含む場合の時間は、これ以上小さくならない
        if ans <= t:
            continue

        # K枚以上ない場合、範囲外のどれかの肉をギリギリ含めることを考える
        # （重複を防ぐため、j > i2 の肉を調べる）
        # 2点からの比が等しい点の軌跡は、c1==c2なら垂直二等分線、それ以外はアポロニウスの円
        # p1-p2, p2-p3, p3-p1 の3円（または直線）が1点で交わる箇所があるか
        # ある → そこに熱源を置き、時間tを算出、t以内に焼ける肉がK以上あるか調べる
        # ない → 他の2点または3点で考えた方がよい
        for i3 in ng:
            if i3 < i2:
                continue
            _, p3, c3 = beefs[i3]
            if c1 == c2:
                if c2 == c3:
                    e = get_circumscribed_center(p1, p2, p3)
                    t = abs(e - p1) * c1
                else:
                    e, t = apollonius_intersections(p3, c3, p1, c1, p2, c2)
            elif c1 == c3:
                e, t = apollonius_intersections(p2, c2, p1, c1, p3, c3)
            else:
                e, t = apollonius_intersections(p1, c1, p2, c2, p3, c3)

            if e is None:
                continue

            t += 1e-8
            ok2 = 0
            for i, p, c in beefs:
                if abs(e - p) * c <= t:
                    ok2 += 1
            if ok2 >= k:
                ans = min(ans, t)

    return ans


n, k = list(map(int, input().split()))
xyc = list(map(int, sys.stdin.read().split()))
print((solve(n, k, xyc)))


import sys
from itertools import combinations
from math import sqrt

read = sys.stdin.read
readline = sys.stdin.readline


def main():
    N, K, *xyc = map(int, read().split())
    x = xyc[::3]
    y = xyc[1::3]
    xy = list(zip(x, y))
    c = xyc[2::3]
    left = 0
    right = 10 ** 6
    delta = 0.1 ** 7
    while right - left > delta:
        mid = (left + right) / 2
        intersections = []
        r = [(mid / i) ** 2 for i in c]
        for i, j in combinations(range(N), 2):
            x1, y1 = xy[i]
            x2, y2 = xy[j]
            X = x2 - x1
            Y = y2 - y1
            XY = X ** 2 + Y ** 2
            r1 = r[i]
            r2 = r[j]

            a = (XY + r1 - r2) / 2
            b = XY * r1 - a ** 2
            if b < delta:
                continue
            b = sqrt(b)
            xi1 = (a * X + Y * b) / XY + x1
            yi1 = (a * Y - X * b) / XY + y1
            xi2 = (a * X - Y * b) / XY + x1
            yi2 = (a * Y + X * b) / XY + y1
            intersections.append((xi1, yi1))
            intersections.append((xi2, yi2))

        intersections.extend(xy)
        cnt = 0
        for X, Y in intersections:
            tmp = 0
            for (i, j), k in zip(xy, r):
                XY = (X - i) ** 2 + (Y - j) ** 2
                if XY < k + delta:
                    tmp += 1
            cnt = max(tmp, cnt)
            if cnt >= K:
                break
        if cnt >= K:
            right = mid
        else:
            left = mid

    print(right)


def __starting_point():
    main()
__starting_point()

import math
def intersectionCC0(x1, y1, r1, r2):
    r = x1**2 + y1**2
    t = (r + r1**2 - r2**2) / (2*r)
    dd = r1**2/r - t**2
    if - (10**-8) < dd < 0: dd = 0
    if dd < 0: return []
    x, y = t * x1, t * y1
    if dd == 0: return [(x, y)]
    sq = math.sqrt(dd)
    dx, dy = y1 * sq, -x1 * sq
    return [(x+dx, y+dy), (x-dx, y-dy)]

def intersectionCC(x1, y1, x2, y2, r1, r2):
    return [(x1+x, y1+y) for x, y in intersectionCC0(x2-x1, y2-y1, r1, r2)]

def chk(t):
    L = [a for a in L0]
    for i, (x1, y1, c1) in enumerate(X):
        for x2, y2, c2 in X[:i]:
            L += intersectionCC(x1, y1, x2, y2, t/c1, t/c2)
    for x0, y0 in L:
        cnt = 0
        for x, y, c in X:
            if math.sqrt((x-x0) ** 2 + (y-y0) ** 2) * c <= t + 10**-8:
                cnt += 1
        if cnt >= K: return 1
    return 0

N, K = map(int, input().split())
X = []
L0 = []
for _ in range(N):
    x, y, c = map(int, input().split())
    X.append((x, y, c))
    L0.append((x, y))

l, r = 0, 150000
while (r-l) * (1<<20) > max(1, l):
    m = (l+r) / 2
    if chk(m):
        r = m
    else:
        l = m
    
print((l+r)/2)

import numpy as np
from scipy.optimize import fmin

n,k=list(map(int,input().split()))
XYC=[list(map(int,input().split())) for i in range(n)]
X,Y,C=[],[],[]
for x,y,c in XYC:
    X.append(x)
    Y.append(y)
    C.append(c)
X=np.array(X,dtype=np.float)
Y=np.array(Y,dtype=np.float)
C=np.array(C,dtype=np.float)
def f(xy):
    x,y=xy
    times=(X-x)*(X-x)+(Y-y)*(Y-y)
    times=C*np.sqrt(times)
    times=np.sort(times)
    return times[k-1]
deff=0.5
ansx=[fmin(f,(x,y),disp=False,ftol=10**(-7),initial_simplex=[(x+deff,y),(x-deff,y+deff),(x-deff,y-deff)]) for x,y,c in XYC]
ansy=list([f(x) for x in ansx])
print((min(ansy)))


N,K = map(int,input().split())
XYC = [tuple(map(int,input().split())) for i in range(N)]

from math import hypot,acos,atan2,cos,sin
def circles_cross_points(x1,y1,r1,x2,y2,r2):
    d = hypot(x1-x2, y1-y2)
    if r1 + r2 < d or abs(r1 - r2) >= d: return []
    x = (r1**2 + d**2 - r2**2) / (2*r1*d)
    if not -1 <= x <= 1: return []
    a = acos(x)
    t = atan2(y2-y1, x2-x1)
    return [
        (x1+cos(t+a)*r1, y1+sin(t+a)*r1),
        (x1+cos(t-a)*r1, y1+sin(t-a)*r1)
    ]

eps = 10e-10
def is_ok(t):
    cands = []
    for x,y,_ in XYC:
        cands.append((x,y))
    for i,(x1,y1,c1) in enumerate(XYC[:-1]):
        for x2,y2,c2 in XYC[i+1:]:
            ps = circles_cross_points(x1,y1,t/c1,x2,y2,t/c2)
            cands += ps
    for cx,cy in cands:
        k = 0
        for x,y,c in XYC:
            d = hypot(cx-x,cy-y)
            if c*d <= t + eps:
                k += 1
                if k >= K:
                    return True
    return False

ok = 10**10
ng = 0
for _ in range(100):
    m = (ok+ng)/2
    if is_ok(m):
        ok = m
    else:
        ng = m
    if ok-ng < 10e-7: break
print(ok)