QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#893783#2794. 妖怪Nt_Yester100 ✓241ms11692kbC++201017b2025-02-10 22:07:292025-02-10 22:07:31

Judging History

This is the latest submission verdict.

  • [2025-02-10 22:07:31]
  • Judged
  • Verdict: 100
  • Time: 241ms
  • Memory: 11692kb
  • [2025-02-10 22:07:29]
  • Submitted

answer

#include <bits/stdc++.h>

#define N 1000005

inline int R() {
    int x=0; bool f=0; char c=getchar();
    while (!isdigit(c)) f|=(c=='-'),c=getchar();
    while (isdigit(c)) x=x*10+c-'0',c=getchar();
    return f?-x:x;
}

template<typename T>
void W(T x,char Extra=0) {
    if (x<0) putchar('-'),x=-x; if (x>9) W(x/10);
    putchar(x%10+'0'); if (Extra) putchar(Extra);
}

using namespace std;
int n,a[N],b[N];

bool check(double mid) {
    double l=1e-7,r=1e9;
    for (int i=1;i<=n;i++) {
        double A=b[i],B=a[i]+b[i]-mid,C=a[i];
        if (B*B-4*A*C<0) return 0;
        auto tmp=sqrt(B*B-4*A*C);
        l=max(l,(-B-tmp)/(2*A)),r=min(r,(-B+tmp)/(2*A));
        if (l>r) return 0;
    }
    return l<=r;
}

int main() {
    n=R();
    for (int i=1;i<=n;i++) a[i]=R(),b[i]=R();
    double l=1,r=1e9,res=0;
    while (r-l>=1e-5) {
        double mid=(l+r)/2;
        if (check(mid)) r=mid,res=mid;
        else l=mid;
    }
    printf("%.4lf\n",res);
    return 0;
}

詳細信息


Pretests


Final Tests

Test #1:

score: 10
Accepted
time: 82ms
memory: 10356kb

input:

500000
3657178 57907114
3611911 58012737
3660889 57898455
3309277 58718883
3635320 57958116
3500353 58273039
3635947 57956653
3591310 58060806
3343924 58638040
3652960 57916956
3555085 58145331
3362740 58594136
3494005 58287851
3706780 57791376
3721720 57756516
3625891 57980117
3429937 58437343
3648...

output:

91920701.7062

result:

ok single line: '91920701.7062'

Test #2:

score: 10
Accepted
time: 232ms
memory: 11676kb

input:

1000000
1 59940527
7 59940524
13 59940521
19 59940518
25 59940515
31 59940512
37 59940509
43 59940506
49 59940503
55 59940500
61 59940497
67 59940494
73 59940491
79 59940488
85 59940485
91 59940482
97 59940479
103 59940476
109 59940473
115 59940470
121 59940467
127 59940464
133 59940461
139 59940458...

output:

91254034.8501

result:

ok single line: '91254034.8501'

Test #3:

score: 10
Accepted
time: 241ms
memory: 11420kb

input:

1000000
1 59940527
10 59940518
19 59940509
28 59940500
37 59940491
46 59940482
55 59940473
64 59940464
73 59940455
82 59940446
91 59940437
100 59940428
109 59940419
118 59940410
127 59940401
136 59940392
145 59940383
154 59940374
163 59940365
172 59940356
181 59940347
190 59940338
199 59940329
208 5...

output:

102660770.8485

result:

ok single line: '102660770.8485'

Test #4:

score: 10
Accepted
time: 236ms
memory: 11680kb

input:

1000000
1 59940527
10 59940518
19 59940509
28 59940500
37 59940491
46 59940482
55 59940473
64 59940464
73 59940455
82 59940446
91 59940437
100 59940428
109 59940419
118 59940410
127 59940401
136 59940392
145 59940383
154 59940374
163 59940365
172 59940356
181 59940347
190 59940338
199 59940329
208 5...

output:

100153114.0334

result:

ok single line: '100153114.0334'

Test #5:

score: 10
Accepted
time: 238ms
memory: 11692kb

input:

1000000
1 59940527
7 59940508
13 59940489
19 59940470
25 59940451
31 59940432
37 59940413
43 59940394
49 59940375
55 59940356
61 59940337
67 59940318
73 59940299
79 59940280
85 59940261
91 59940242
97 59940223
103 59940204
109 59940185
115 59940166
121 59940147
127 59940128
133 59940109
139 59940090...

output:

109484150.9475

result:

ok single line: '109484150.9475'

Test #6:

score: 10
Accepted
time: 0ms
memory: 5964kb

input:

2
4 1
1 4

output:

10.0000

result:

ok single line: '10.0000'

Test #7:

score: 10
Accepted
time: 154ms
memory: 11440kb

input:

1000000
7937091 58451012
7735995 58484528
7868181 58462497
7914315 58454808
7945623 58449590
7987881 58442547
7524759 58519734
7978047 58444186
7684587 58493096
7930143 58452170
7726995 58486028
7726785 58486063
7754739 58481404
7934691 58451412
7960005 58447193
7625835 58502888
7966749 58446069
787...

output:

132881044.8876

result:

ok single line: '132881044.8876'

Test #8:

score: 10
Accepted
time: 140ms
memory: 11496kb

input:

1000000
7183862 68671050
8486526 65473602
8301704 65927256
8276283 65989653
7175403 68691813
7288989 68413011
7825943 67095033
8400880 65683824
7512894 67863426
7868920 66989544
7157451 68735877
7441218 68039358
8251115 66051429
8441613 65583843
7650746 67525062
8353910 65799114
8472358 65508378
842...

output:

121366739.9409

result:

ok single line: '121366739.9409'

Test #9:

score: 10
Accepted
time: 135ms
memory: 11516kb

input:

1000000
3972077 57055848
3955399 57089204
3968841 57062320
3955175 57089652
3959939 57080124
3990735 57018532
3934027 57131948
3973203 57053596
3959987 57080028
3950363 57099276
3997537 57004928
3969701 57060600
3991049 57017904
3854731 57290540
3801553 57396896
3959975 57080052
3828957 57342088
392...

output:

91999998.9234

result:

ok single line: '91999998.9234'

Test #10:

score: 10
Accepted
time: 135ms
memory: 11552kb

input:

1000000
2974217 67064460
2843709 67390730
2981699 67045755
2934215 67164465
2974229 67064430
2993945 67015140
2942201 67144500
2924699 67188255
2981289 67046780
2939855 67150365
2991589 67021030
2841703 67395745
2948187 67129535
2716489 67708780
2862705 67343240
2965837 67085410
2936647 67158385
288...

output:

101333334.8741

result:

ok single line: '101333334.8741'