Submission #25477

#	Time	Username	Problem	Language	Result	Execution time	Memory
25477		leejseo	먼 별 (KOI16_dist)	Pypy 2	0 / 100	2 ms	0 KiB

dist

class Star:
    def __init__(self, x, y, dx, dy):
        self.x = x
        self.y = y
        self.dx = dx
        self.dy = dy
    
    def place(self, t):
        x = self.x
        y = self.y
        dx = self.dx
        dy = self.dy
        return [ x + t * dx , y + t * dy]
    def dist(self, P, t):
        P1 = self.place(t)
        P2 = P.place(t)
        x1, y1 = P1[0], P1[1]
        x2, y2 = P2[0], P2[1]
        return (x2 - x1)**2 + (y2 - y1)**2

def g(L, t):
    n = len(L)
    cnt = 0
    for i in range(n):
        for j in range(i):
            temp = L[i].dist(L[j], t)
            if temp > cnt: 
                cnt = temp
    return cnt

def f(L, P):
    lo = 0
    hi = P
    while (lo <= hi):
        llh = (2*lo + hi)//3
        lhh = (lo + 2*hi + 1)//3       
        if g(L, llh) <= g(L, lhh):
            hi = lhh-1
        else:
            lo = llh+1
    return [lo, g(L, lo)]

def main():
    n, T = map(int, raw_input().split())
    L = []
    for i in range(n):
        x, y, dx, dy = map(int, raw_input().split())
        L.append(Star(x, y, dx, dy))
    k = f(L, T)
    print k[0]
    print k[1]
    return
main()

• Subtask 1: 0 / 2
• Subtask 2: 0 / 40
• Subtask 3: 0 / 39
• Subtask 4: 0 / 19