naval.py

import math
import random
import sys

# 2-D point with some helpful methods like addition of two points, multiplication by number,
#  distance to other point etc
class Point(object):

    def __init__(self, x=0, y=0):
        self.x = x
        self.y = y

    def __str__(self):
        return '(%g, %g)' % (self.x, self.y)

    def __repr__(self):
        return self.__str__()

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

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

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

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

    def __eq__(self, other):
        return (self.x == other.x) and (self.y == other.y)

    def rad(self):
        return math.hypot(self.x, self.y)

    def dist(self, other):
        return math.hypot(self.x - other.x, self.y - other.y)

def dist(a, b):
    return a.dist(b)

def rad(a):
    return a.rad()

# Circle defined by O - center and r - radius
class Circle(object):

    def __init__(self, O=Point(), r=1):
        self.O = O
        self.r = r

    def __str__(self):
        return 'circle ' + '(' + str(self.O) + ', ' + str(self.r) + ')'

    def __repr__(self):
        return self.__str__()

    # check if point lies inside the circle
    def contains(self, x):
        return dist(self.O, x) <= self.r

# Ship defined by p - starting point and v - velocity
class Ship(object):

    def __init__(self, p=Point(), v=0):
        self.p = p
        self.v = v

    def __str__(self):
        return 'ship at ' + str(self.p) + ' with v = ' + str(self.v)

    def __repr__(self):
        return self.__str__()

# Place p and time t to encounter
class Encounter(object):

    def __init__(self, p = Point(), t=0):
        self.p = p
        self.t = t

    def __str__(self):
        return 'encounter at ' + str(self.p) + ' in t = ' + str(self.t)

    def __repr__(self):
        return self.__str__()

    def __eq__(self, other):
        return self.p == other.p and self.t == other.t

    # if a ship x can make it to the encounter point in time t we say that encounter contains this ship
    def contains(self, x):
        return dist(self.p, x.p) <= self.t*x.v

# if all the speeds are equal the problem becomes the smallest circle problem
# the following two functions were created to solve this problem,
# but they are still useful to handle special cases in the general problem

# smallest circle for 2 points
def circle_by2(a, b):
    return Circle((a + b)/2, dist(a, b)/ 2)

# smallest circle for 3 points
def circle_by3(a, b, c):
    D = 2*(a.x*(b.y - c.y) + b.x*(c.y - a.y) + c.x*(a.y - b.y))
    if D == 0:
        C = circle_by2(a, b)
        if not C.contains(c):
            if dist(a, c) > dist(b, c):
                C = circle_by2(a, c)
            else: C = circle_by2(b, c)
        return C
    Ox = 1/D*(rad(a)**2*(b.y - c.y) + rad(b)**2*(c.y - a.y) + rad(c)**2*(a.y - b.y))
    Oy = 1/D*(rad(a)**2*(c.x - b.x) + rad(b)**2*(a.x - c.x) + rad(c)**2*(b.x - a.x))
    O = Point(Ox, Oy)
    r = dist(O, a)
    return Circle(Point(Ox, Oy), r)

# a and b are ships with different non-zero velocities
# find the circle - set of points which a and b can reach in same time
def meet_circle(a, b):
    av2 = a.v**2
    bv2 = b.v**2
    vsdiff = bv2 - av2
    ox = (a.p.x*bv2 - b.p.x*av2)/vsdiff
    oy = (a.p.y*bv2 - b.p.y*av2)/vsdiff
    r2 = (av2*b.p.rad()**2 - bv2*a.p.rad()**2)/vsdiff + ox**2 + oy**2
    r = math.sqrt(r2)
    return Circle(Point(ox, oy), r)

# intersection of two circles (a and b are circles)
def int_circle_circle(a, b):
    D = dist(a.O, b.O)
    if (D > a.r + b.r) or (D < abs(a.r - b.r)):
        return []
    d = 1/4*math.sqrt((D + a.r + b.r)*(D + a.r - b.r)*
                          (D - a.r + b.r)*(-D + a.r + b.r))
    xm = (a.O.x + b.O.x)/2 + (b.O.x - a.O.x)*(a.r**2 - b.r**2)/(2*D**2)
    xd = 2*(a.O.y - b.O.y)/(D**2)*d
    x1 = xm + xd
    x2 = xm - xd
    ym = (a.O.y + b.O.y)/2 + (b.O.y - a.O.y)*(a.r**2 - b.r**2)/(2*D**2)
    yd = 2*(a.O.x - b.O.x)/(D**2)*d
    y1 = ym - yd
    y2 = ym + yd
    p1 = Point(x1, y1)
    p2 = Point(x2, y2)
    if p1 == p2:
        return [p1]
    else:
        return [p1, p2]

# encounter for two ships with non-zero velocities
def enc_by2(a, b):
    p = (a.p*b.v + b.p*a.v)/(a.v + b.v)
    t = dist(a.p, p)/a.v
    return Encounter(p, t)

# encounter for 3 three ships
# works only in case if known that all 3 ships
# will come at the same time
def enc_by3(a, b, c):

    # same speed for all
    if a.v == b.v and a.v == c.v:
        if a.v == 0:
            print('Error: two ships with zero velocities at different points:' +
                  str(a) + 'and' + str(b), file=sys.stderr)
            return []
        else:
            crcl = circle_by3(a.p, b.p, c.p)
            return Encounter(crcl.O, crcl.r/a.v)
    # reassign in a way that a.v != a.v and a.v != c.v
    # because different vel -> meet at circle, not line
    if a.v == b.v:
        [a, b, c] = [c, a, b]
    elif a.v == c.v:
        [a, b, c] = [b, a, c]
    crcl_ab = meet_circle(a, b)
    crcl_ac = meet_circle(a, c)
    crcl_int = int_circle_circle(crcl_ab, crcl_ac)
    if len(crcl_int) == 1:
        p = crcl_int[0]
    else:
        if (dist(a.p, crcl_int[0]) < dist(a.p, crcl_int[1])):
            p = crcl_int[0]
        else:
            p = crcl_int[1]
    t = dist(a.p, p)/a.v
    return Encounter(p, t)

# encounter for ships P + [q1, q2] (P is a list of ships)
# knowing that q1 and q2 will come last
def enc_2known(P, q1, q2):
    enc = enc_by2(q1, q2)
    for p in P:
        if not enc.contains(p):
            enc = enc_by3(q1, q2, p)
    return enc

# encounter for ships P + [q]
# knowing that q will come last
def enc_1known(P, q):
    if len(P) == 0:
        return Encounter(q.p, 0)
    random.shuffle(P)
    enc = enc_by2(q, P[0])
    # print("P = " + str(P) + "\nenc = " + str(enc))
    for i in range(1, len(P)):
        if not enc.contains(P[i]):
            enc = enc_2known(P[0:i], P[i], q)
    return enc

# encounter for ships P
def find_enc(P):
    if len(P) == 1:
        return Encounter(P[0].p, 0)

    # point of a ship with v = 0 will be assigned to this variable
    zero_point = False
    for i in range(0, len(P)):
        p = P[i]
        if p.v == 0:
            # if no ship with zero v found before
            if not zero_point:
                zero_point = p.p
                zero_ind = [i]
            # there was already a ship with v = 0, in different point
            elif zero_point != p.p:
                return Encounter(Point(0, 0), math.inf)
            # just in case, if found a ship with zero v in the same point
            elif zero_point == p.p:
                zero_ind.append(i)

    # found a single ship with zero v
    if bool(zero_point):
        # not to override P
        # P exept zero-v Ships
        P_no0 = [P[i] for i in range(0, len(P)) if not zero_ind.__contains__(i)]
        # define the time of the latest ship to come to zero_point
        t = 0
        for p in P_no0:
            this_t = dist(p.p, zero_point)/p.v
            if this_t > t:
                t = this_t
        return Encounter(zero_point, t)

    random.shuffle(P)
    enc = enc_by2(P[0], P[1])
    # print("P = " + str(P) + "\nenc = " + str(enc))
    for i in range(2, len(P)):
        if not enc.contains(P[i]):
            enc = enc_1known(P[0:i], P[i])
    return enc


#chr_inpt = "3  0.0   0.0   1.0   2.0   0.0   2.0   1.0   2.0   3.0"
#chr_inpt = "4  0.0  1.1  1.0  1.1  0.0  1.0  -1.1  0.0  1.0  0.0  -1.1  1.0"
#inpt = [float(x) for x in chr_inpt.split()]

inpt = [float(x) for x in input().split()]

n = inpt[0]
l = inpt[1:]
arr = [l[i:i + 3] for i in range(0, len(l), 3)]

# arr = np.array([[np.random.random() for i in range(3)] for j in range(100)])
P = list(map(lambda x: Ship(Point(x[0], x[1]), abs(x[2])), arr))

enc = find_enc(P)
print(format(enc.t, '#.3f'))