Problem p02764 (python)

Fixed submission:
#!/usr/bin/env python3
import sys
INF = float("inf")

tol = 1e-9


def ctc(x1, y1, r1, x2, y2, r2):
    # 二つの円の共通接線の数
    # common tangent count?
    # common tangent of circle?
    # 2円の関係性は、
    # 同一(=INF), 離れている(=4)、外接(=3)、交わる(=2)、内接(=1)、内包(=0)がある
    tol = 1e-9
    # r1 <= r2として一般性を失わない
    if r2 < r1:
        x1, x2 = x2, x1
        y1, y2 = y2, y1
        r1, r2 = r2, r1

    d = ((x1-x2)**2 + (y1-y2)**2)**0.5

    if x1 == x2 and y1 == y2 and d < tol:
        # 同一の円
        return INF
    elif (d - (r2+r1)) > tol:
        # 離れている
        return 4
    elif (d - (r2+r1)) > -tol:
        # 外接している
        return 3
    elif (d-(r2-r1)) > tol:
        # 交わっている
        return 2
    elif (d-(r2-r1)) > -tol:
        # 内接している
        return 1
    else:
        # 内包している
        return 0


def inner(x1, y1, c1, x2, y2, c2):
    coeff1 = c1/(c1+c2)
    coeff2 = c2/(c1+c2)
    b = (x1*coeff1+x2*coeff2, y1*coeff1+y2*coeff2)
    return b


def intersection(x1, y1, r1, x2, y2, r2):
    status = ctc(x1, y1, r1, x2, y2, r2)

    if not (1 <= status <= 3):
        return []
    elif status == 3:
        # 外接している場合
        return [inner(x1, y1, r1, x2, y2, r2)]
    elif status == 1:
        # 内接している場合
        return [(x1 + r1*(x1-x2)/d, y1 + r1*(y1-y2)/d)]
    else:
        # 交わっている場合
        L = ((x1-x2)**2 + (y1-y2)**2)**0.5
        cos = ((L**2+r1**2)-r2**2)/(2*r1*L)
        e1 = ((x2-x1)/L, (y2-y1)/L)
        e2 = (-(y2-y1)/L, (x2-x1)/L)
        P1H = ((r1*cos/L)*(x2-x1), (r1*cos/L)*(y2-y1))
        ah = (r1**2-(r1*cos)**2)**0.5
        HA = (e2[0]*ah, e2[1]*ah)
        A = (x1 + P1H[0]+HA[0], y1+P1H[1]+HA[1])
        B = (x1 + P1H[0]-HA[0], y1+P1H[1]-HA[1])
        return [A, B]


def circle_in(x, y, x1, y1, r1):
    tol = 1e-9
    L = (x1-x)**2 + (y1-y)**2
    R = r1**2
    LR = L-R

    if LR > tol:
        return False
    elif LR > -tol:
        return True
    else:
        return True


def solve(N: int, K: int, x: "List[int]", y: "List[int]", c: "List[int]"):

    # 時刻Tの時点でK枚以上の肉が焼ける熱源の配置はあるか

    left = 0
    right = 2000*max(c)
    for _ in range(300):
        if right - left < tol:
            break
        mid = (left + right)/2
        yakiniku = 0
        for i in range(N):
            for j in range(i+1, N):
                b = intersection(x[i], y[i], mid/c[i], x[j], y[j], mid/c[j])
                for xx, yy in b:
                    count = [circle_in(xx, yy, x[k], y[k], mid/c[k])
                             for k in range(N)]
                    if yakiniku < sum(count):
                        yakiniku = max(yakiniku, sum(count))
        for i in range(N):
            count = [circle_in(x[i], y[i], x[k], y[k], mid/c[k])
                     for k in range(N)]
            if yakiniku < sum(count):
                yakiniku = max(yakiniku, sum(count))
        # print(left, right, mid)
        # for i in range(N):
        #     print("(x-({}))^2+(y-({}))^2=({})^2".format(
        #         x[i], y[i], mid/c[i]))
        if yakiniku >= K:
            right = mid
        else:
            left = mid

    print(mid)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]"
    y = [int()] * (N)  # type: "List[int]"
    c = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(N, K, x, y, c)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
import cmath
import math
INF = float("inf")

EPS = 1e-9


def ctc(p1, r1, p2, r2):
    # 二つの円の共通接線の数
    # common tangent count?
    # common tangent of circle?
    # 2円の関係性は、
    # 同一(=INF), 離れている(=4)、外接(=3)、交わる(=2)、内接(=1)、内包(=0)がある
    # r1 <= r2として一般性を失わない
    if r2 < r1:
        p1, p2 = p2, p1
        r1, r2 = r2, r1

    d = abs(p1-p2)

    if p1 == p2 and d < EPS:    # 同一の円
        return INF
    elif (d - (r2+r1)) > EPS:   # 離れている
        return 4
    elif (d - (r2+r1)) > -EPS:  # 外接している
        return 3
    elif (d-(r2-r1)) > EPS:     # 交わっている
        return 2
    elif (d-(r2-r1)) > -EPS:    # 内接している
        return 1
    else:                       # 内包している
        return 0


def inner(p1, c1, p2, c2):
    coeff1 = c1/(c1+c2)
    coeff2 = c2/(c1+c2)
    return p1*coeff1+p2*coeff2


def intersection(p1, r1, p2, r2):
    status = ctc(p1, r1, p2, r2)
    d = abs(p1-p2)
    if not (1 <= status <= 3):
        return []
    elif status == 3:           # 外接
        return [inner(p1, r1, p2, r2)]
    elif status == 1:           # 内接
        return [p1 + r1*(p1-p2)/d]
    else:                       # 交わっている場合
        if r1 > r2:
            p1, p2 = p2, p1
            r1, r2 = r2, r1
        d = abs(p1-p2)
        cos = (r1**2+d**2-r2**2)/(2*r1*d)
        angle = math.acos(cos)
        phi = cmath.phase(p2-p1)
        return [
            p1 + cmath.rect(r1, phi+angle),
            p1 + cmath.rect(r1, phi-angle)
        ]


def circle_in(p, o, r1, allow_on_edge=True):
    if allow_on_edge:
        return abs(o-p)-r1 < EPS
    else:
        return abs(o-p)-r1 < -EPS


def solve(N: int, K: int, x: "List[int]", y: "List[int]", c: "List[int]"):

    # 時刻Tの時点でK枚以上の肉が焼ける熱源の配置はあるか
    comp = [complex(xx, yy) for xx, yy in zip(x, y)]

    left = 0
    right = 2000*max(c)
    while right - left > EPS:
        mid = (left + right)/2
        yakiniku = 0
        b = comp.copy()
        for i in range(N):
            for j in range(i+1, N):
                b.extend(intersection(comp[i], mid/c[i], comp[j], mid/c[j]))

        for p in b:
            count = [circle_in(p, comp[k], mid/c[k])
                     for k in range(N)]
            yakiniku = max(yakiniku, sum(count))
        if yakiniku >= K:
            right = mid
        else:
            left = mid

    print(mid)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]"
    y = [int()] * (N)  # type: "List[int]"
    c = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(N, K, x, y, c)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
INF = float("inf")


def isclose(a, b, tol=1e-9):
    return abs(a-b) < tol


def solve(N: int, K: int, x: "List[int]", y: "List[int]", c: "List[int]"):

    # 時刻Tの時点でK枚以上の肉が焼ける熱源の配置はあるか
    def inner(x1, y1, c1, x2, y2, c2):
        coeff1 = c1/(c1+c2)
        coeff2 = c2/(c1+c2)
        b = (x1*coeff1+x2*coeff2, y1*coeff1+y2*coeff2)
        return b

    def circle_cross(x1, y1, r1, x2, y2, r2):
        L = ((x1-x2)**2 + (y1-y2)**2)**0.5
        x, y = inner(x1, y1, r1, x2, y2, r2)
        if r1+r2 < L:
            return []
        elif isclose(r1+r2, L):
            return [(x, y)]
        elif L < abs(r1-r2):
            return []
        else:
            cos = ((L**2+r1**2)-r2**2)/(2*r1*L)
            e1 = ((x2-x1)/L, (y2-y1)/L)
            e2 = (-(y2-y1)/L, (x2-x1)/L)
            P1H = ((r1*cos/L)*(x2-x1), (r1*cos/L)*(y2-y1))
            ah = (r1**2-(r1*cos)**2)**0.5
            HA = (e2[0]*ah, e2[1]*ah)
            A = (x1 + P1H[0]+HA[0], y1+P1H[1]+HA[1])
            B = (x1 + P1H[0]-HA[0], y1+P1H[1]-HA[1])
            # print("solve (x-({}))^2+(y-({}))^2==({})^2,(x-({}))^2+(y-({}))^2==({})^2"
            #       .format(x1, y1, r1, x2, y2, r2))
            # print(A, B)
            return [A, B]

    def circle_in(x, y, x1, y1, r1):
        L = (x1-x)**2 + (y1-y)**2
        R = r1**2
        if R >= L:
            return True
        elif isclose(R, L):
            return True
        else:
            return False

    # print(circle_cross(0, 0, 5, 4, 3, 5))
    # return

    left = -1
    right = ((max(x)-min(x))**2+(max(y)-min(y))**2)**0.7
    for _ in range(100):
        # while right - left > 1:
        mid = (left + right)/2
        yakiniku = 0
        for i in range(N):
            for j in range(i+1, N):
                # print("(i, j)", i, j)
                b = circle_cross(x[i], y[i], mid/c[i], x[j], y[j], mid/c[j])
                # print(b)
                for xx, yy in b:
                    # print("--")
                    # print((xx, yy))
                    count = [circle_in(xx, yy, x[k], y[k], mid/c[k])
                             for k in range(N)]
                    if yakiniku < sum(count):
                        yakiniku = max(yakiniku, sum(count))
                        # print(count, xx, yy)
        # for k in range(N):
        #     print("(x-({}))^2+(y-({}))^2==({})^2"
        #           .format(x[k], y[k], mid/c[k]))
        # print("(l, r)", left, right, mid, yakiniku)
        if yakiniku >= K:
            right = mid
        else:
            left = mid

    print(mid)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]"
    y = [int()] * (N)  # type: "List[int]"
    c = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(N, K, x, y, c)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
import math
INF = float("inf")


def solve(N: int, K: int, x: "List[int]", y: "List[int]", c: "List[int]"):

    # 時刻Tの時点でK枚以上の肉が焼ける熱源の配置はあるか
    def inner(x1, y1, c1, x2, y2, c2):
        coeff1 = c1/(c1+c2)
        coeff2 = c2/(c1+c2)
        b = (x1*coeff1+x2*coeff2, y1*coeff1+y2*coeff2)
        return b

    def circle_cross(x1, y1, r1, x2, y2, r2):
        L = ((x1-x2)**2 + (y1-y2)**2)**0.5
        x, y = inner(x1, y1, r1, x2, y2, r2)
        if r1+r2 < L:
            return []
        elif math.isclose(r1+r2, L):
            return [(x, y)]
        elif L < abs(r1-r2):
            return []
        else:
            cos = ((L**2+r1**2)-r2**2)/(2*r1*L)
            e1 = ((x2-x1)/L, (y2-y1)/L)
            e2 = (-(y2-y1)/L, (x2-x1)/L)
            P1H = ((r1*cos/L)*(x2-x1), (r1*cos/L)*(y2-y1))
            ah = (r1**2-(r1*cos)**2)**0.5
            HA = (e2[0]*ah, e2[1]*ah)
            A = (x1 + P1H[0]+HA[0], y1+P1H[1]+HA[1])
            B = (x1 + P1H[0]-HA[0], y1+P1H[1]-HA[1])
            # print("solve (x-({}))^2+(y-({}))^2==({})^2,(x-({}))^2+(y-({}))^2==({})^2"
            #       .format(x1, y1, r1, x2, y2, r2))
            # print(A, B)
            return [A, B]

    def circle_in(x, y, x1, y1, r1):
        L = (x1-x)**2 + (y1-y)**2
        R = r1**2
        if R >= L:
            return True
        elif math.isclose(R, L):
            return True
        else:
            return False

    # print(circle_cross(0, 0, 5, 4, 3, 5))
    # return

    left = -1
    right = ((max(x)-min(x))**2+(max(y)-min(y))**2)**0.7
    for _ in range(100):
        # while right - left > 1:
        mid = (left + right)/2
        yakiniku = 0
        for i in range(N):
            for j in range(i+1, N):
                # print("(i, j)", i, j)
                b = circle_cross(x[i], y[i], mid/c[i], x[j], y[j], mid/c[j])
                # print(b)
                for xx, yy in b:
                    # print("--")
                    # print((xx, yy))
                    count = [circle_in(xx, yy, x[k], y[k], mid/c[k])
                             for k in range(N)]
                    if yakiniku < sum(count):
                        yakiniku = max(yakiniku, sum(count))
                        # print(count, xx, yy)
        # for k in range(N):
        #     print("(x-({}))^2+(y-({}))^2==({})^2"
        #           .format(x[k], y[k], mid/c[k]))
        # print("(l, r)", left, right, mid, yakiniku)
        if yakiniku >= K:
            right = mid
        else:
            left = mid

    print(mid)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]"
    y = [int()] * (N)  # type: "List[int]"
    c = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(N, K, x, y, c)


if __name__ == '__main__':
    main()