Submission #69874708

---

Source Code Expand

from math import lcm, sqrt


def dist(x1, y1, x2, y2):
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2))


e = 10**-9


def calc_pos(Sx, Sy, Gx, Gy, t, dx, dy, p):
    if p >= t:
        return Gx, Gy
    return Sx + p * dx, Sy + p * dy


def solve(TSx, TSy, TGx, TGy, ASx, ASy, AGx, AGy):
    Tt = dist(TSx, TSy, TGx, TGy)
    At = dist(ASx, ASy, AGx, AGy)
    Tdx, Tdy = (TGx - TSx), (TGy - TSy)
    Adx, Ady = (AGx - ASx), (AGy - ASy)
    z = Tdx * Ady - Tdy * Adx
    f = Tdx * Adx
    g = Tdy * Ady
    Tdx /= Tt
    Tdy /= Tt
    Adx /= At
    Ady /= At
    if z == 0 and f >= 0 and g >= 0:
        t = min(Tt, At)
        TSx, TSy = TSx + t * Tdx, TSy + t * Tdy
        ASx, ASy = ASx + t * Adx, ASy + t * Ady
        Tt = dist(TSx, TSy, TGx, TGy)
        At = dist(ASx, ASy, AGx, AGy)
        Tdx, Tdy = (TGx - TSx), (TGy - TSy)
        Adx, Ady = (AGx - ASx), (AGy - ASy)
        if Tt > e:
            Tdx /= Tt
            Tdy /= Tt
        if At > e:
            Adx /= At
            Ady /= At

    def calc(p):
        Tx, Ty = calc_pos(TSx, TSy, TGx, TGy, Tt, Tdx, Tdy, p)
        Ax, Ay = calc_pos(ASx, ASy, AGx, AGy, At, Adx, Ady, p)
        return dist(Tx, Ty, Ax, Ay)

    l = 0
    r = max(Tt, At)
    while r - l > e:
        d = (r - l) / 3
        ln = l + d
        rn = ln + d
        lv = calc(ln)
        rv = calc(rn)
        if lv <= rv:
            r = rn
        if rv <= lv:
            l = ln

    return calc(l)


def main():
    T = int(input())
    for t in range(T):
        TSx, TSy, TGx, TGy = map(int, input().split())
        ASx, ASy, AGx, AGy = map(int, input().split())
        ans = solve(TSx, TSy, TGx, TGy, ASx, ASy, AGx, AGy)
        print(ans)


main()

Submission Info

Judge Result