Problem:
 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

Solution (Python):
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)


if __name__ == '__main__':
    main()

Solution (Python):
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)


if __name__ == '__main__':
    main()

Solution (Python):
from math import hypot
N, K = map(int, input().split())
def count(x, y, T, cs):
    r = 0
    for a, b, c in cs:
        r += int(hypot(x-a, y-b) <= T/c + 10**-8)

    return r

def ko(x1, y1, r1, r2):
    
    a = (x1**2 + y1**2 + r1**2 - r2**2)/2

    t = (x1**2+y1**2)*r1**2-a**2
    if t < 0:
        return -1

    x = a*x1
    xb = y1*t**(1/2)
    y = a*y1
    yb = x1*t**(1/2)
    b = x1**2+y1**2
    return ((x+xb)/b, (y-yb)/b), ((x-xb)/b, (y+yb)/b)

def zko(x1, y1, r1, x2, y2, r2):
    r = ko(x2-x1, y2-y1, r1, r2)
    if r == -1:
        return -1
    (xp, yp), (xm, ym) = ko(x2-x1, y2-y1, r1, r2)
    return (xp+x1, yp+y1), (xm+x1, ym+y1)

def f(T, cs):
    ccs = []
    for i in range(N):
        (xi, yi, ci) = cs[i]
        for j in range(i+1, N):
            (xj, yj, cj) = cs[j]
            r = zko(xi, yi, T/ci, xj, yj, T/cj)

            if r == -1:
                continue
            (x1, y1), (x2, y2) = r

            ccs.append((x1, y1))
            ccs.append((x2, y2))
    for a, b, c in cs:
        ccs.append((a, b))

    for x, y in ccs:
        if count(x, y, T, cs) >= K:
            return True
    return False




cs = []
for i in range(N):
    x, y, c = map(int, input().split())
    cs.append((x, y, c))
mx, mn = 10**9, -1
idx = mx/2
for _ in range(100):
    if f(idx, cs):
        idx, mx = (idx+mn)/2, idx
        continue
    idx, mn = (idx+mx)/2, idx
print(idx)

Solution (Python):


import sys
from math import hypot

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class Geometry:
    """ 幾何学計算用クラス """

    def __init__(self, EPS):
        self.EPS = EPS

    def add(self, a, b):
        x1, y1 = a
        x2, y2 = b
        return (x1+x2, y1+y2)

    def sub(self, a, b):
        x1, y1 = a
        x2, y2 = b
        return (x1-x2, y1-y2)

    def mul(self, a, b):
        x1, y1 = a
        if not isinstance(b, tuple):
            return (x1*b, y1*b)
        x2, y2 = b 
        return (x1*x2, y1*y2)

    def div(self, a, b):
        x1, y1 = a
        if not isinstance(b, tuple):
            return (x1/b, y1/b)
        x2, y2 = b
        return (x1/x2, y1/y2)

    def abs(self, a):
        from math import hypot
        x1, y1 = a
        return hypot(x1, y1)

    def norm(self, a):
        x, y = a
        return x**2 + y**2

    def dot(self, a, b):
        x1, y1 = a
        x2, y2 = b
        return x1*x2 + y1*y2

    def cross(self, a, b):
        x1, y1 = a
        x2, y2 = b
        return x1*y2 - y1*x2

    def project(self, seg, p):
        """ 線分segに対する点pの射影 """

        p1, p2 = seg
        base = self.sub(p2, p1)
        r = self.dot(self.sub(p, p1), base) / self.norm(base)
        return self.add(p1, self.mul(base, r))

    def reflect(self, seg, p):
        """ 線分segを対称軸とした点pの線対称の点 """

        return self.add(p, self.mul(self.sub(self.project(seg, p), p), 2))

    def ccw(self, p0, p1, p2):
        """ 線分p0,p1から線分p0,p2への回転方向 """

        a = self.sub(p1, p0)
        b = self.sub(p2, p0)
        
        if self.cross(a, b) > self.EPS: return 1
        
        if self.cross(a, b) < -self.EPS: return -1
        
        if self.dot(a, b) < -self.EPS: return 2
        
        if self.norm(a) < self.norm(b): return -2
        
        return 0

    def intersect(self, seg1, seg2):
        """ 線分seg1と線分seg2の交差判定 """

        p1, p2 = seg1
        p3, p4 = seg2
        return (
            self.ccw(p1, p2, p3) * self.ccw(p1, p2, p4) <= 0
            and self.ccw(p3, p4, p1) * self.ccw(p3, p4, p2) <= 0
        )

    def get_distance_LP(self, line, p):
        """ 直線lineと点pの距離 """

        p1, p2 = line
        return abs(self.cross(self.sub(p2, p1), self.sub(p, p1)) / self.abs(self.sub(p2, p1)))

    def get_distance_SP(self, seg, p):
        """ 線分segと点pの距離 """

        p1, p2 = seg
        if self.dot(self.sub(p2, p1), self.sub(p, p1)) < 0: return self.abs(self.sub(p, p1))
        if self.dot(self.sub(p1, p2), self.sub(p, p2)) < 0: return self.abs(self.sub(p, p2))
        return self.get_distance_LP(seg, p)

    def get_distance_SS(self, seg1, seg2):
        """ 線分seg1と線分seg2の距離 """

        p1, p2 = seg1
        p3, p4 = seg2
        if self.intersect(seg1, seg2): return 0
        return min(
            self.get_distance_SP(seg1, p3), self.get_distance_SP(seg1, p4),
            self.get_distance_SP(seg2, p1), self.get_distance_SP(seg2, p2),
        )

    def get_cross_pointSS(self, seg1, seg2):
        """ 線分seg1と線分seg2の交点 """

        p1, p2 = seg1
        p3, p4 = seg2
        base = self.sub(p4, p3)
        dist1 = abs(self.cross(base, self.sub(p1, p3)))
        dist2 = abs(self.cross(base, self.sub(p2, p3)))
        t = dist1 / (dist1+dist2)
        return self.add(p1, self.mul(self.sub(p2, p1), t))
    
    def intersectCL(self, c, line):
        """ 円cと直線lineの交差判定 """

        x, y, r = c
        return self.get_distance_SP(line, (x, y)) <= r

    def get_cross_pointCL(self, c, line):
        """ 円cと直線lineの交点 """
        from math import sqrt

        if not self.intersectCL(c, line): return -1
        x, y, r = c
        p1, p2 = line
        pr = self.project(line, (x, y))
        e = self.div(self.sub(p2, p1), self.abs(self.sub(p2, p1)))
        base = sqrt(r*r - self.norm(self.sub(pr, (x, y))))
        return [self.add(pr, self.mul(e, base)), self.sub(pr, self.mul(e, base))]
    
    def arg(self, p):
        from math import atan2
        x, y = p
        return atan2(y, x)
    
    def polar(self, a, r):
        from math import sin, cos
        return (cos(r)*a, sin(r)*a)
    
    def intersectCC(self, c1, c2):
        """ 円c1と円c2の交差判定 """
        from math import hypot

        x1, y1, r1 = c1
        x2, y2, r2 = c2
        return hypot(x1-x2, y1-y2) <= r1 + r2
    
    def get_cross_pointCC(self, c1, c2):
        """ 円c1と円c2の交点 """
        from math import acos

        if not self.intersectCC(c1, c2): return -1
        x1, y1, r1 = c1
        x2, y2, r2 = c2
        try:
            d = self.abs(self.sub((x1, y1), (x2, y2)))
            a = acos((r1*r1+d*d-r2*r2) / (2*r1*d))
            t = self.arg(self.sub((x2, y2), (x1, y1)))
            return [self.add((x1, y1), self.polar(r1, t+a)), self.add((x1, y1), self.polar(r1, t-a))]
        except:
            return -1

def bisearch_min(mn, mx, func, EPS):
    """ 条件を満たす最小値を見つける二分探索(小数用) """

    ok = mx
    ng = mn
    while ng+EPS < ok:
        mid = (ok+ng) / 2
        if func(mid):
            
            ok = mid
        else:
            
            ng = mid
    return ok

gm = Geometry(10**-8)


def calc(t):

    
    ccls = []
    
    XY = []
    for x, y, c in XYC:
        
        XY.append((x, y))
        
        r = t / c
        ccls.append((x, y, r))

    
    for i in range(N):
        ccl1 = ccls[i]
        for j in range(i+1, N):
            ccl2 = ccls[j]
            
            res =  gm.get_cross_pointCC(ccl1, ccl2)
            if res != -1:
                XY.append(res[0])
                XY.append(res[1])

    
    mx = 0
    for x, y in XY:
        cnt = 0
        for x2, y2, r in ccls:
            
            if hypot(x-x2, y-y2) <= r + gm.EPS:
                cnt += 1
        mx = max(mx, cnt)

    return mx >= K

N, K = MAP()
XYC = []
for i in range(N):
    x, y, c = MAP()
    XYC.append((x, y, c))


res = bisearch_min(0.0, 10**9, calc, 10**-8)
print(res)

Solution (Python):
from math import atan2, cos, sin

EPS = 1e-7


def hypot(a):
    return sum(x ** 2 for x in a) ** 0.5


def scale(s, v):
    assert isinstance(s, int) or isinstance(s, float)
    return [s * v[0], s * v[1], s * v[2]]


def dot(a, b):
    return a[0] * b[0] + a[1] * b[1] + a[2] * b[2]


def add(a, b):
    return [a[0] + b[0], a[1] + b[1], a[2] + b[2]]


def sub(a, b):
    return [a[0] - b[0], a[1] - b[1], a[2] - b[2]]


def matmul(mat, v):
    return [dot(row, v) for row in mat]


def rotZ(theta):
    return [[cos(theta), -sin(theta), 0], [sin(theta), cos(theta), 0], [0, 0, 1]]


def _circleCircleIntersection(R, d, r):
    
    
    
    
    
    
    
    
    if d == 0:
        return [(0, 0)]
    x = (R ** 2 - r ** 2 + d ** 2) / (2 * d)
    ySq = R ** 2 - x ** 2
    if ySq == 0:
        return [(x, 0)]
    elif ySq > 0:
        y = ySq ** 0.5
        
        
        return [(x, y), (x, -y)]
    else:
        raise AssertionError()


def circleCircleIntersection(x1, y1, r1, x2, y2, r2):
    
    
    
    v1 = [x1, y1, 0]
    v2 = [x2, y2, 0]
    d = hypot(sub(v2, v1))
    if r1 + r2 < d:
        
        return []
    if min(r1, r2) + d < max(r1, r2):
        
        return []

    
    offset = list(v1)
    v1 = sub(v1, offset)
    v2 = sub(v2, offset)
    assert v1[0] == 0 and v1[1] == 0

    
    angle = -atan2(v2[1], v2[0])
    v2 = matmul(rotZ(angle), v2)
    assert abs(v2[1]) < EPS

    ret = []
    for pt in _circleCircleIntersection(r1, v2[0], r2):
        pt = [pt[0], pt[1], 0]
        
        pt = matmul(rotZ(-angle), pt)
        
        pt = add(pt, offset)
        ret.append((pt[0], pt[1]))

    return ret


def circleCircleIntersection(x1, y1, r1, x2, y2, r2):
    
    v1 = [x1, y1, 0]
    v2 = [x2, y2, 0]
    d = hypot(sub(v2, v1))
    if r1 + r2 < d:
        
        return []
    if min(r1, r2) + d < max(r1, r2):
        
        return []
    if d == 0:
        return [(x1, y1)]

    
    u = scale(1 / d, sub(v2, v1))
    
    a = (r1 ** 2 - r2 ** 2 + d ** 2) / (2 * d)
    
    mid = add(v1, scale(a, u))

    
    uPerpendicular = [u[1], -u[0], 0]
    
    h = (r1 ** 2 - a ** 2) ** 0.5
    
    ret1 = add(mid, scale(h, uPerpendicular))
    ret2 = add(mid, scale(-h, uPerpendicular))
    return [[ret1[0], ret1[1]], [ret2[0], ret2[1]]]


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


def numMeat(t):
    
    
    intersect = []
    for i in range(len(XYC)):
        x1, y1, c1 = XYC[i]
        r1 = t / c1
        for j in range(i + 1, len(XYC)):
            x2, y2, c2 = XYC[j]
            r2 = t / c2
            pts = circleCircleIntersection(x1, y1, r1, x2, y2, r2)
            intersect.extend(pts)
        intersect.append((x1, y1))

    if False:
        import matplotlib.pyplot as plt

        plt.figure()
        ax = plt.gca()
        ax.cla()
        bound = t // 5
        ax.set_xlim((-bound, bound))
        ax.set_ylim((-bound, bound))

        for i in range(len(XYC)):
            x1, y1, c1 = XYC[i]
            r1 = t / c1
            ax.add_artist(plt.Circle((x1, y1), r1, color="blue", fill=False))
        for x, y in intersect:
            ax.plot([x], [y], ".", color="red")
        plt.show()

    best = 0
    for pt in intersect:
        count = 0
        for x, y, c in XYC:
            if c * ((x - pt[0]) ** 2 + (y - pt[1]) ** 2) ** 0.5 <= t + EPS:
                count += 1
        best = max(best, count)

    return best


lo = 0

hi = max(c * (x ** 2 + y ** 2) ** 0.5 for x, y, c in XYC)
while hi - lo > EPS:
    mid = (hi + lo) / 2
    if numMeat(mid) >= K:
        hi = mid
    else:
        lo = mid
print(hi)

Solution (Python):
from math import atan2, cos, sin

EPS = 1e-7


def hypot(a):
    return sum(x ** 2 for x in a) ** 0.5


def dot(a, b):
    return a[0] * b[0] + a[1] * b[1] + a[2] * b[2]


def add(a, b):
    return [a[0] + b[0], a[1] + b[1], a[2] + b[2]]


def sub(a, b):
    return [a[0] - b[0], a[1] - b[1], a[2] - b[2]]


def matmul(mat, v):
    return [dot(row, v) for row in mat]


def rotZ(theta):
    return [[cos(theta), -sin(theta), 0], [sin(theta), cos(theta), 0], [0, 0, 1]]


def _circleCircleIntersection(R, d, r):
    
    
    
    
    
    
    
    
    if d == 0:
        return [(0, 0)]
    x = (R ** 2 - r ** 2 + d ** 2) / (2 * d)
    ySq = R ** 2 - x ** 2
    if ySq == 0:
        return [(x, 0)]
    elif ySq > 0:
        y = ySq ** 0.5
        
        
        return [(x, y), (x, -y)]
    else:
        raise AssertionError()


def circleCircleIntersection(x1, y1, r1, x2, y2, r2):
    
    
    
    v1 = [x1, y1, 0]
    v2 = [x2, y2, 0]
    d = hypot(sub(v2, v1))
    if r1 + r2 < d:
        
        return []
    if min(r1, r2) + d < max(r1, r2):
        
        return []

    
    offset = list(v1)
    v1 = sub(v1, offset)
    v2 = sub(v2, offset)
    assert v1[0] == 0 and v1[1] == 0

    
    angle = -atan2(v2[1], v2[0])
    v2 = matmul(rotZ(angle), v2)
    assert abs(v2[1]) < EPS

    ret = []
    for pt in _circleCircleIntersection(r1, v2[0], r2):
        pt = [pt[0], pt[1], 0]
        
        pt = matmul(rotZ(-angle), pt)
        
        pt = add(pt, offset)
        ret.append((pt[0], pt[1]))

    return ret


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


def numMeat(t):
    
    
    intersect = []
    for i in range(len(XYC)):
        x1, y1, c1 = XYC[i]
        r1 = t / c1
        for j in range(i + 1, len(XYC)):
            x2, y2, c2 = XYC[j]
            r2 = t / c2
            pts = circleCircleIntersection(x1, y1, r1, x2, y2, r2)
            intersect.extend(pts)
        intersect.append((x1, y1))

    best = 0
    for pt in intersect:
        count = 0
        for x, y, c in XYC:
            if c * ((x - pt[0]) ** 2 + (y - pt[1]) ** 2) ** 0.5 <= t + EPS:
                count += 1
        best = max(best, count)

    return best


lo = 0

hi = max(c * (x ** 2 + y ** 2) ** 0.5 for x, y, c in XYC)
while hi - lo > EPS:
    mid = (hi + lo) / 2
    if numMeat(mid) >= K:
        hi = mid
    else:
        lo = mid
print(hi)

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1
EPS = 1.0e-8

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Circle:
    def __init__(self, x, y, r):
        self.x = x
        self.y = y
        self.r = r

    def center(self):
        return Point(self.x, self.y)

    def intersection(self, c):
        d = self.center().distance(c.center())
        if d > self.r + c.r:
            return None
        
        if d < abs(self.r - c.r):
            return None
        
        if d == 0 and self.r == c.r:
            return None
        else:
            a = (self.r**2 - c.r**2 + d**2) / (2*d)
            h = math.sqrt(self.r**2-a**2 + sys.float_info.epsilon)
            x2 = self.x+a*(c.x-self.x)/d
            y2 = self.y+a*(c.y-self.y)/d
            x3 = x2+h*(c.y-self.y)/d
            y3 = y2-h*(c.x-self.x)/d

            x4 = x2-h*(c.y-self.y)/d
            y4 = y2+h*(c.x-self.x)/d

            return Point(x3, y3), Point(x4, y4)

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def distance(self, p):
        return math.sqrt((self.x - p.x)**2 + (self.y - p.y)**2)

class Bisect:
    def __init__(self, func):
        self.__func = func


    def bisect_left(self, x, lo, hi):
        while hi - lo > EPS:
            mid = (lo+hi)/2
            if self.__func(mid) < x:
                lo = mid
            else:
                hi = mid
        return lo

@mt
def slv(N, K, XYC):
    def f(t):
        cs = []
        for x, y, c in XYC:
            cs.append(Circle(x, y, t / c))

        cand = [c.center() for c in cs]
        for i, j in combinations(range(N), r=2):
            p = cs[i].intersection(cs[j])
            if p:
                cand.append(p[0])
                cand.append(p[1])

        ans = 0
        for p in cand:
            tmp = 0
            for c in cs:
                d = c.center().distance(p)
                if d - EPS < c.r:
                    tmp += 1
            ans = max(ans, tmp)
        return ans

    b = Bisect(f)
    return b.bisect_left(K, 0, 10000000)


def main():
    N, K = read_int_n()
    XYC = [read_int_n() for _ in range(N)]
    print(slv(N, K, XYC))


if __name__ == '__main__':
    main()

Solution (Python):
import sys

input = sys.stdin.buffer.readline
import math
from itertools import combinations
EPS = 10**-7


class P2():
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.norm2 = (self.x**2 + self.y**2)**0.5

    def __add__(self, other):
        return P2(self.x + other.x, self.y + other.y)

    def __sub__(self, other):
        return P2(self.x - other.x, self.y - other.y)

    def __mul__(self, other: float):
        return P2(self.x * other, self.y * other)

    def __truediv__(self, other: float):
        return P2(self.x / other, self.y / other)

    def dot(self, other):
        return self.x * other.x + self.y * other.y

    def det(self, other):
        return self.x * other.y - self.y * other.x


class Circle():
    def __init__(self, p, r):
        self.p = p
        self.r = r


n, k = map(int, input().split())
p = []
c = []
for _ in range(n):
    x, y, cc = map(float, input().split())
    p.append(P2(x, y))
    c.append(cc)

dist = [[(p[i] - p[j]).norm2 for j in range(n)] for i in range(n)]


def check(r):
    circles = [Circle(p[i], r / c[i]) for i in range(n)]

    
    cand = [pi for pi in p]
    for c_i, c_j in combinations(circles, r=2):
        d_ij = c_i.p - c_j.p
        if d_ij.norm2 < c_i.r + c_j.r - EPS:
            
            x = (c_j.r**2 - c_i.r**2 + d_ij.norm2**2) / (2 * d_ij.norm2)
            h = math.sqrt(max(c_j.r**2 - x**2, 0.0))
            v = P2(-d_ij.y, d_ij.x) * (h / d_ij.norm2)
            dx = c_j.p + d_ij * (x / d_ij.norm2)
            cand.append(dx + v)
            cand.append(dx - v)

    for cand_p in cand:
        cnt = 0
        for c_i in circles:
            if (c_i.p - cand_p).norm2 < c_i.r + EPS:
                cnt += 1
                if cnt >= k:
                    return True

    return False


lb = 0.0  
ub = 3000 * 100  
while ub - lb > EPS:
    mid = (ub + lb) / 2
    if check(mid):
        ub = mid
    else:
        lb = mid

print(ub)

Solution (Python):
import sys

input = sys.stdin.buffer.readline
import math
EPS = 10**-7


class P2():
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.norm2 = (self.x**2 + self.y**2)**0.5

    def __add__(self, other):
        return P2(self.x + other.x, self.y + other.y)

    def __sub__(self, other):
        return P2(self.x - other.x, self.y - other.y)

    def __mul__(self, other: float):
        return P2(self.x * other, self.y * other)

    def __truediv__(self, other: float):
        return P2(self.x / other, self.y / other)

    def dot(self, other):
        return self.x * other.x + self.y * other.y

    def det(self, other):
        return self.x * other.y - self.y * other.x


n, k = map(int, input().split())
p = []
c = []
for _ in range(n):
    x, y, cc = map(float, input().split())
    p.append(P2(x, y))
    c.append(cc)

dist = [[(p[i] - p[j]).norm2 for j in range(n)] for i in range(n)]


def check(r):
    r_c = tuple(r / c[i] for i in range(n))
    
    cand = [pi for pi in p]
    for i in range(n - 1):
        for j in range(i + 1, n):
            d_ij = p[i] - p[j]

            if dist[i][j] < r_c[i] + r_c[j] - EPS:
                
                x = ((r_c[j])**2 -
                     (r_c[i])**2 + d_ij.norm2**2) / (2 * d_ij.norm2)
                h = math.sqrt(max((r_c[j])**2 - x**2, 0.0))
                v = P2(-d_ij.y, d_ij.x) * (h / d_ij.norm2)
                dx = p[j] + d_ij * (x / d_ij.norm2)
                cand.append(dx + v)
                cand.append(dx - v)

    for cand_p in cand:
        cnt = 0
        for i in range(n):
            if (p[i] - cand_p).norm2 < r_c[i] + EPS:
                cnt += 1
                if cnt >= k:
                    return True

    return False


lb = 0.0  
ub = 3000 * 100  
while ub - lb > EPS:
    mid = (ub + lb) / 2
    if check(mid):
        ub = mid
    else:
        lb = mid

print(ub)

Solution (Python):
import cmath
EPS = 1e-8





n, k = map(int, input().split())
d = []
for _ in range(n):
	x, y, c = list(map(int, input().split()))
	d.append((complex(x, y), c))

ok, ng = 10**6, 0
for _ in range(60):
	t = (ok+ng)/2
	

	res = 1
	
	for i in range(n):
		o1, r1 = d[i][0], t / d[i][1]
		cnt0 = 1
		for j in range(n):
			if j == i:
				continue
			o2, r2 = d[j][0], t / d[j][1]
			if abs(o1 - o2) + EPS <= r2:
				cnt0 += 1

		res = max(res, cnt0)
		for j in range(i+1, n):
			o2, r2 = d[j][0], t / d[j][1]
			if abs(o1 - o2) - EPS >= r1 + r2:
				
				continue
			elif abs(o1 - o2) + min(r1, r2) + EPS <= max(r1, r2):
				continue
			else:
				co = (r1**2 - r2**2 + abs(o1 - o2)**2) / (2 * abs(o1 - o2) * r1)
				si = cmath.sqrt(1 - co**2)
				p1 = o1 + (o2 - o1) * (co + 1j * si) * r1 / abs(o1 - o2)
				p2 = o1 + (o2 - o1) * (co - 1j * si) * r1 / abs(o1 - o2)				

			cnt1, cnt2 = 2, 2
			for l in range(n):
				if l == i or l == j:
					continue
				else:
					o3, r3 = d[l][0], t / d[l][1]
					if abs(p1 - o3) + EPS <= r3:
						cnt1 += 1
					if abs(p2 - o3) + EPS <= r3:
						cnt2 += 1
			
			res = max(res, cnt1, cnt2)

	
	if res >= k:
		ok = t
	else:
		ng = t

if ok < 1e-6:
	print(0)
else:
	print(ok)

Solution (Python):
import sys

input = sys.stdin.buffer.readline
import math
EPS = 10**-7


class P2():
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.norm2 = (self.x**2 + self.y**2)**0.5

    def __add__(self, other):
        return P2(self.x + other.x, self.y + other.y)

    def __sub__(self, other):
        return P2(self.x - other.x, self.y - other.y)

    def smul(self, a):
        return P2(self.x * a, self.y * a)

    def dot(self, other):
        return self.x * other.x + self.y * other.y

    def det(self, other):
        return self.x * other.y - self.y * other.x


n, k = map(int, input().split())
p = []
c = []
for _ in range(n):
    x, y, cc = map(float, input().split())
    p.append(P2(x, y))
    c.append(cc)

dist = [[(p[i] - p[j]).norm2 for j in range(n)] for i in range(n)]


def check(r):
    r_c = tuple(r / c[i] for i in range(n))
    
    cand = [pi for pi in p]
    for i in range(n - 1):
        for j in range(i + 1, n):
            d_ij = p[i] - p[j]

            if dist[i][j] < r_c[i] + r_c[j] - EPS:
                
                x = ((r_c[j])**2 -
                     (r_c[i])**2 + d_ij.norm2**2) / (2 * d_ij.norm2)
                h = math.sqrt(max((r_c[j])**2 - x**2, 0.0))
                v = P2(-d_ij.y, d_ij.x).smul(h / d_ij.norm2)
                dx = p[j] + d_ij.smul(x / d_ij.norm2)
                cand.append(dx + v)
                cand.append(dx - v)

    for cand_p in cand:
        cnt = 0
        for i in range(n):
            if (p[i] - cand_p).norm2 < r_c[i] + EPS:
                cnt += 1
                if cnt >= k:
                    return True

    return False


lb = 0.0  
ub = 3000 * 100  
while ub - lb > EPS:
    mid = (ub + lb) / 2
    if check(mid):
        ub = mid
    else:
        lb = mid

print(ub)

Solution (Python):
import sys
input = sys.stdin.readline


class Vec:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __str__(self):
        return '({}, {})'.format(self.x, self.y)

    def __add__(self, other):
        return Vec(self.x+other.x, self.y+other.y)

    def __sub__(self, other):
        return Vec(self.x-other.x, self.y-other.y)

    def __mul__(self, k):
        return Vec(self.x*k, self.y*k)

    def __truediv__(self, k):
        return Vec(self.x/k, self.y/k)

    def abs(self):
        return (self.x**2 + self.y**2)**.5


def dist(p, q):
    return (p-q).abs()




def intersection_circles(c1, r1, c2, r2):
    d = (c1-c2).abs()

    
    if r1 + r2 < d:
        return []

    
    if d < abs(r2 - r1):
        return []

    x = (r1**2-r2**2+d**2) / (2*d)
    y = (r1**2-x**2)**.5
    e1 = (c2-c1) / (c2-c1).abs()
    e2 = Vec(-e1.y, e1.x)
    p1 = c1 + e1*x + e2*y
    p2 = c1 + e1*x - e2*y
    return [p1, p2]


N, K = map(int, input().split())
center = [None] * N
cost = [0] * N
for i in range(N):
    x, y, c = map(int, input().split())
    center[i] = Vec(x, y)
    cost[i] = c
lb = 0
ub = 10**6
EPS = 10**(-8)
while ub - lb > EPS:
    mid = (lb + ub) / 2
    r = [mid / c for c in cost]
    points = list(center)
    for i in range(N-1):
        for j in range(i+1, N):
            points += intersection_circles(center[i], r[i], center[j], r[j])
    cnt = 0
    for p in points:
        tmp = 0
        for i in range(N):
            if dist(p, center[i]) < r[i] + EPS:
                tmp += 1
        cnt = max(cnt, tmp)
    if cnt >= K:
        ub = mid
    else:
        lb = mid
print(lb)