QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#87350 | #5505. Great Chase | chiranko# | TL | 0ms | 0kb | Python3 | 815b | 2023-03-12 17:58:07 | 2023-03-12 17:58:10 |
Judging History
answer
import decimal
from decimal import *
decimal.getcontext().prec=20
cases = int(input())
for _ in range(cases):
n, vv = input().split()
n = int(n)
vv = Decimal(vv)
p = [0 for _ in range(n)]
v = [0 for _ in range(n)]
for i in range(n):
p[i], v[i] = map(Decimal, input().split())
l, r = Decimal(0.0), Decimal(2e12)
while r - l > 1e-9:
mid = (l + r) / 2
maxl, minr = Decimal(-1e12-1), Decimal(1e12+1)
for i in range(n):
if p[i] < 0:
maxl = max(maxl, p[i] + mid * v[i])
else:
minr = min(minr, p[i] - mid * v[i])
if maxl > minr:
r = mid
else:
l = mid
res = vv * l
print(res.quantize(Decimal("1.000000000000")))
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
3 4 9 10 2 -7 2 -6 1 7 1 2 8 -1 7 1 6 2 3 -1000000000000 1 1000000000000 1
output:
38.249999999626 1.230769230021