QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#87349#5505. Great Chasechiranko#TL 15ms8976kbPython3816b2023-03-12 17:49:072023-03-12 17:49: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:49:10]
  • 评测
  • 测评结果:TL
  • 用时:15ms
  • 内存:8976kb
  • [2023-03-12 17:49:07]
  • 提交

answer

import decimal
from decimal import *

decimal.getcontext().prec=30

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-12:
        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")))

详细

Test #1:

score: 100
Accepted
time: 15ms
memory: 8976kb

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.249999999999
1.230769230769
3000000000000.000000000000

result:

ok 3 numbers

Test #2:

score: -100
Time Limit Exceeded

input:

10000
200 997007
405524182320 754760
686939601648 419804
687047488212 715566
1446157132 4594
-670522037 4673
763634629282 253755
424307411732 275041
1582708381 8473
-667425982 4622
-522841486 1427
702430907988 460271
1405423646 1060
1497754648 6227
883363410675 723547
56899800372 46435
-810216390 64...

output:

145405766328.349109325608
16414958969.727280460716
5202715639.835183573441
321977234.156325340786
45384199210.221683415549
183885744.769230752421
1708925225.230472021448
89786664971.557942005040
13924365606.287388203685
412975327.555555497289
965508404.512101212859
4703493416.288376164304
352961619....

result: