oj.uz

Submission #26031

# Submission time Handle Problem Language Result Execution time Memory
26031 2017-06-26T16:35:36 Z leejseo None (KOI16_dist) Python 2
2 / 100
 2000 ms 16 KB 
import sys
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):
        return [ self.x + t * self.dx , self.y + t * self.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)*(x2 - x1) + (y2 - y1)*(y2 - y1)
 
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)]
 

n, T = map(int, sys.stdin.readline().split())
L = [None]*n
for i in range(n):
    x, y, dx, dy = map(int, sys.stdin.readline().split())
    L[i] = Star(x, y, dx, dy)
k = f(L, T)
print k[0]
print k[1]

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2 KB Output is correct
2 Correct 18 ms 2 KB Output is correct
3 Correct 16 ms 2 KB Output is correct
4 Correct 15 ms 2 KB Output is correct
5 Correct 20 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 14 ms 2 KB Output is correct
9 Correct 15 ms 2 KB Output is correct
10 Correct 20 ms 2 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2 KB Output is correct
2 Correct 18 ms 2 KB Output is correct
3 Correct 16 ms 2 KB Output is correct
4 Correct 15 ms 2 KB Output is correct
5 Correct 20 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 14 ms 2 KB Output is correct
9 Correct 15 ms 2 KB Output is correct
10 Correct 20 ms 2 KB Output is correct
11 Execution timed out 2056 ms 3 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 39.0

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

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2 KB Output is correct
2 Correct 18 ms 2 KB Output is correct
3 Correct 16 ms 2 KB Output is correct
4 Correct 15 ms 2 KB Output is correct
5 Correct 20 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 14 ms 2 KB Output is correct
9 Correct 15 ms 2 KB Output is correct
10 Correct 20 ms 2 KB Output is correct
11 Execution timed out 2056 ms 3 KB Time limit exceeded
12 Halted 0 ms 0 KB -