QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#105041#5505. Great ChasekingstonduyTL 5ms7976kbPython3784b2023-05-12 21:08:342023-05-12 21:08:38

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-12 21:08:38]
  • 评测
  • 测评结果:TL
  • 用时:5ms
  • 内存:7976kb
  • [2023-05-12 21:08:34]
  • 提交

answer

tc= int(input())
while(tc != 0):
    tc-=1
    n,v= map(float, input().split())
    a=[]
    for i in range (int(n)):
        pi, vi = map(float, input().split())
        a.append((pi, vi))
    l=0
    r=1e12
    res=0
    e= 0.0000000001
    cnt = 1000
    while(l<=r and l+e < r and cnt != 0):
        cnt-=1
        mid= (l+r)/2
        ls= -1e18
        rs= 1e18
        for i in range (int(n)):
            temp1, temp2= a[i]
            dis= temp2 * mid
            if(temp1 < 0):
                ls=max(ls, temp1 + dis)
            else:
                rs= min(rs, temp1 - dis)
        if(ls <= rs):
            res= max(res, mid)
            l= mid+e
        else:
            r= mid-e
    output = "{:.10f}".format(res * v)
    print(output)

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 5ms
memory: 7976kb

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.2499999987
1.2307692292
3000000000000.0000000000

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.3489990234
16414958969.7272777557
5202715639.8351545334
321977234.1562350988
45384199210.2216644287
183885744.7692267895
1708925225.2303857803
89786664971.5578155518
13924365606.2872714996
412975327.5555295944
965508404.5120820999
4703493416.2883739471
352961619.3810160756
5575125771.79...

result: