QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#87350#5505. Great Chasechiranko#TL 0ms0kbPython3815b2023-03-12 17:58:072023-03-12 17:58:10

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-12 17:58:10]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2023-03-12 17:58:07]
  • 提交

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

result: