oj.uz

Submission #31198

# Submission time Handle Problem Language Result Execution time Memory
31198 2017-08-13T08:59:54 Z leejseo None (KOI16_dist) Python 2
2 / 100
 2000 ms 20 KB 
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 CCW(P, P1, P2):
    x1, y1 = P[0], P[1]
    x2, y2 = P1[0], P1[1]
    x3, y3 = P2[0], P2[1]
    Area = (x2 - x1) * (y3 - y1) - (y2 - y1) * ( x3 - x1)
    Abs = abs(Area)
    if Area == 0 : return 0
    return Area / Abs 

def ConvexHull(L, t):
    n = len(L)
    cor = [ i.place(t) for i in L]
    cor.sort()
    UP = []
    LO = []
    for q in cor:
        while len(UP) > 1 and CCW(UP[-2], UP[-1], q) >= 0: UP.pop()
        while len(LO) > 1 and CCW(LO[-2], LO[-1], q) <= 0: LO.pop()
        UP.append(q)
        LO.append(q)
    return UP, LO

def RotCal(M, t):
    U, L = ConvexHull(M, t)
    i = 0
    j = len(L)-1
    while i < len(U)-1 or j > 0:
        if i==len(U)-1 : j-= 1
        elif j == 0: i += 1
        elif (U[i+1][1] - U[i][1])*(L[j][0] - L[j-1][0]) > \
             (L[j][1] - L[j-1][1]) *(U[i+1][0] - U[i][0]): i+= 1
        else: j-= 1
    x1, y1 = U[i][0], U[i][1]
    x2, y2 = L[j][0], L[j][1]
    return (x2 - x1)**2 + (y2 - y1)**2

def g(L, t):
    return RotCal(L, t)

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
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2 KB Output is correct
2 Correct 14 ms 2 KB Output is correct
3 Correct 16 ms 2 KB Output is correct
4 Correct 19 ms 2 KB Output is correct
5 Correct 15 ms 2 KB Output is correct
6 Correct 19 ms 2 KB Output is correct
7 Correct 15 ms 2 KB Output is correct
8 Correct 18 ms 2 KB Output is correct
9 Correct 15 ms 2 KB Output is correct
10 Correct 16 ms 2 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2 KB Output is correct
2 Correct 14 ms 2 KB Output is correct
3 Correct 16 ms 2 KB Output is correct
4 Correct 19 ms 2 KB Output is correct
5 Correct 15 ms 2 KB Output is correct
6 Correct 19 ms 2 KB Output is correct
7 Correct 15 ms 2 KB Output is correct
8 Correct 18 ms 2 KB Output is correct
9 Correct 15 ms 2 KB Output is correct
10 Correct 16 ms 2 KB Output is correct
11 Incorrect 381 ms 3 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2024 ms 20 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2 KB Output is correct
2 Correct 14 ms 2 KB Output is correct
3 Correct 16 ms 2 KB Output is correct
4 Correct 19 ms 2 KB Output is correct
5 Correct 15 ms 2 KB Output is correct
6 Correct 19 ms 2 KB Output is correct
7 Correct 15 ms 2 KB Output is correct
8 Correct 18 ms 2 KB Output is correct
9 Correct 15 ms 2 KB Output is correct
10 Correct 16 ms 2 KB Output is correct
11 Incorrect 381 ms 3 KB Output isn't correct
12 Halted 0 ms 0 KB -