QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#187546#3854. RadarFlying2018#WA 234ms15088kbC++143.6kb2023-09-24 17:59:162023-09-24 17:59:18

Judging History

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

  • [2023-09-24 17:59:18]
  • 评测
  • 测评结果:WA
  • 用时:234ms
  • 内存:15088kb
  • [2023-09-24 17:59:16]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define db double
using namespace std;

const db eps=1e-7;
const db inf=1e20;

int sgn (db x){
    if(fabs(x)<eps)return 0;
    if(x<0)return -1;
    return 1;
}
int comp (double x,double y){
    return sgn(x-y);
}
bool Less(double x,double y){
    return comp(x,y)==-1;
}

const int MAXN=2e5+7;

struct point{
    double x,y;
    point(){};
    point(db _x,db _y):x(_x),y(_y){};
    double operator^(const point &b)const {
        return x * b.y - y *b.x;
    }
    double operator*(const point &b){
        return x * b.x + y * b.y;
    }
    point operator+(const point &b)const {
        return point(x+b.x,y+b.y);
    }    
    point operator-(const point &b)const {
        return point(x-b.x,y-b.y);
    }
    point operator*(const double &k)const{
        return point(x*k,y*k);
    }
    point operator/(const double &k)const{
        return point(x/k,y/k);
    }
    double len2()
    {
        return x*x+y*y;
    }
    double len(){
        return hypot(x,y);
    }
    double distance(point p){
        return hypot(x-p.x,y-p.y);
    }
}a[MAXN];
struct Line {
    point p;
    point v;
    double rad;
    Line(){};

    Line(point _p,point _v):p(_p),v(_v){
        rad = atan2(v.y,v.x);
    };

    bool operator<(const Line &x){
        return Less(rad,x.rad);
    }
    
    point lineprog(point a){
        return p+(((v-p)*((v-p)*(a-p)))/(v-p).len2());
    }
}b[MAXN];

bool cmprad(Line A,Line B){
    return Less(A.rad,B.rad);
}

int R,F,N;
db rl[MAXN];
db nans;

inline void calc(point a,db d,point b){
    // printf("%lf %lf -> b\n",a.x/a.len()*d,a.y/a.len()*d);
    point a0 = point(a.x/a.len()*d,a.y/a.len()*d);
    nans=min(nans,a0.distance(b));
}


inline void check(Line a,point b){
    // printf("%lf %lf ?!\n",a.v.x,a.v.y);
    point tmp = a.lineprog(b);
    // printf("%lf %lf %lf %lf\n",b.x,b.y,tmp.x,tmp.y);
    int t= lower_bound(rl+1,rl+R+1,tmp.len()) - rl;
    // printf("%lf %d\n",b.len(),rl[t]);
    calc(a.v,rl[1],b);
    calc(a.v,rl[R],b);
    if(t!=R+1){
        if(t<R)calc(a.v,rl[t+1],b);
        if(t<R-1)calc(a.v,rl[t+2],b);
        calc(a.v,rl[t],b);
        if(t>1)calc(a.v,rl[t-1],b);
        if(t>2)calc(a.v,rl[t-2],b);
    }
}

inline void solve(){

    for(int i=1;i<=N;++i){
        if(F==1){
            nans=1e18;
            check(b[1],a[i]);
            printf("%.12lf\n",nans);
            continue;
        }      
        int t = lower_bound(b+1,b+F+1,Line(point(0,0),a[i])) - b;
        nans=1e18;
        check(b[1],a[i]);
        check(b[F],a[i]); 
        check(b[2],a[i]);  
        check(b[F-1],a[i]);     
        if(!(t==F+1 || t==1)){
            check(b[t],a[i]);
            check(b[t-1],a[i]);
            if(t!=F)check(b[t+1],a[i]);
            if(t!=2)check(b[t-2],a[i]);
        }
        printf("%.12lf\n",nans);
    }
    return ;
}

int main(){
    scanf("%d%d%d",&R,&F,&N);
    for(int i=1;i<=R;++i){
        scanf("%lf",&rl[i]);
    }
    sort(rl+1,rl+R+1);
    for(int i=1;i<=F;++i){
        scanf("%lf%lf",&a[i].x,&a[i].y);
        b[i]=Line(point(0.0,0.0),point(a[i].x,a[i].y));
    }
    sort(b+1,b+F+1,cmprad);
    // printf("%lf %lf %lf %lf\n",atan2(3,0),atan2(-2,0),atan2(0,3),atan2(0,-3));
    // for(int i=1;i<=F;++i){
    //     printf("%lf %lf\n",b[i].v.x,b[i].v.y);
    // }
    for(int i=1;i<=N;++i){
        scanf("%lf%lf",&a[i].x,&a[i].y);
    }
    solve();
    return 0;
}
/*

3 1 1
1 2 3
3 3
1 -2


3 7 5
2
4
7
8 4
2 8
-1 5
-7 2
-4 -4
1 -8
6 -3
3 -1
8 1
2 6
-5 2
-1 -1

*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 8292kb

input:

3 8 4
2
4
7
1 0
2 1
0 1
-1 1
-5 -2
-5 -6
-2 -7
6 -1
-1 -1
3 1
-5 -3
8 1

output:

0.605291072917
0.977772290466
1.551845105402
1.414213562373

result:

ok 4 numbers

Test #2:

score: 0
Accepted
time: 1ms
memory: 8148kb

input:

1 8 32
7
0 1
1 0
0 -1
-1 0
1 -1
-1 1
-1 -1
1 1
20 10
10 20
-20 10
10 -20
-10 20
20 -10
-10 -20
-20 -10
2 1
1 2
-2 1
1 -2
-1 2
2 -1
-1 -2
-2 -1
5 0
0 5
-5 0
0 -5
5 5
5 -5
-5 5
-5 -5
9 0
0 9
-9 0
0 -9
9 9
9 -9
-9 9
-9 -9

output:

15.874985099258
15.874985099258
15.874985099258
15.874985099258
15.874985099258
15.874985099258
15.874985099258
15.874985099258
4.929656701046
4.929656701046
4.929656701046
4.929656701046
4.929656701046
4.929656701046
4.929656701046
4.929656701046
2.000000000000
2.000000000000
2.000000000000
2.00000...

result:

ok 32 numbers

Test #3:

score: 0
Accepted
time: 0ms
memory: 8244kb

input:

3 4 1681
16
8
4
-1 0
0 -1
0 1
1 0
-9 17
-4 -7
2 -13
-11 -17
15 -19
-7 1
-8 14
-8 -7
-8 20
-16 -3
12 14
-3 12
9 -5
-18 11
3 -1
2 0
-18 0
0 -19
-1 -19
18 -8
2 20
5 -8
-8 -19
-9 -16
20 -19
14 -1
3 10
-1 -4
4 10
16 17
19 -7
-17 4
1 -12
-5 -12
-5 -10
-15 -5
-10 -19
-2 -10
-4 -16
-2 4
-14 8
-17 16
4 1
16 ...

output:

9.055385138137
4.123105625618
3.605551275464
11.045361017187
15.297058540778
1.414213562373
8.246211251235
7.000000000000
8.944271909999
3.000000000000
12.165525060596
5.000000000000
5.099019513593
11.180339887499
1.414213562373
2.000000000000
2.000000000000
3.000000000000
3.162277660168
8.246211251...

result:

ok 1681 numbers

Test #4:

score: 0
Accepted
time: 3ms
memory: 8056kb

input:

3 4 1681
16
8
4
-1 -1
1 -1
-1 1
1 1
17 1
13 7
-13 -18
-1 18
4 -12
-9 3
5 10
-10 1
-12 -4
14 10
-18 19
0 -3
-7 3
-16 11
-15 9
16 1
-8 -12
3 1
0 -2
15 -18
-14 20
9 -19
17 12
20 5
-3 -6
12 -1
9 10
-13 -9
-20 -15
-11 6
17 -2
-10 -19
15 -8
-6 17
18 15
2 -3
18 -12
8 -3
-11 -6
19 -15
20 0
3 4
2 -16
-6 -17
...

output:

11.777372119304
4.631593682590
6.895656100977
12.291422905367
6.555964003581
4.270304206047
4.392536000448
6.367825885745
6.555964003581
2.990316379371
10.187520359495
2.833626166509
2.977064831365
4.696779860162
4.352239888693
11.328455809797
3.384030147710
1.836459365744
2.947251516416
7.635131895...

result:

ok 1681 numbers

Test #5:

score: 0
Accepted
time: 1ms
memory: 6024kb

input:

1 4 16
7
0 1
1 0
0 -1
-1 0
3 0
0 3
-3 0
0 -3
3 3
3 -3
-3 3
-3 -3
8 0
0 8
-8 0
0 -8
8 8
8 -8
-8 8
-8 -8

output:

4.000000000000
4.000000000000
4.000000000000
4.000000000000
5.000000000000
5.000000000000
5.000000000000
5.000000000000
1.000000000000
1.000000000000
1.000000000000
1.000000000000
8.062257748299
8.062257748299
8.062257748299
8.062257748299

result:

ok 16 numbers

Test #6:

score: 0
Accepted
time: 0ms
memory: 8220kb

input:

30 4 120
128
1
2
256
4
512
1024
2048
8
4096
32768
131072
262144
524288
8192
268167
16
536334
16384
1047
32
2095
8380
64
134083
65536
4190
67041
33520
16760
536334 0
-536335 0
0 536334
0 -536335
-1 1
-2 2
-4 4
-8 8
-16 16
-32 32
-64 64
-128 128
-256 256
-512 512
-1024 1024
-2048 2048
-4096 4096
-8192...

output:

1.000000000000
2.000000000000
4.000000000000
8.000000000000
16.000000000000
32.000000000000
64.000000000000
128.000000000000
256.000000000000
512.000000000000
1024.000000000000
2048.000000000000
4096.000000000000
8192.000000000000
16384.000000000000
32768.000000000000
65536.000000000000
131072.00000...

result:

ok 120 numbers

Test #7:

score: 0
Accepted
time: 3ms
memory: 6248kb

input:

4 4 1681
1000
1
999000
999
999000 999000
-999001 999000
999000 -999001
-999001 -999001
9 2
-17 -3
15 3
-19 -6
-6 -16
19 6
-12 -16
1 4
4 12
4 -15
-1 -17
5 7
12 13
19 -19
6 -16
-9 -19
6 -10
1 -20
18 17
-2 -20
13 -13
2 -7
13 14
-15 -7
7 -2
-3 4
-15 11
13 -15
20 -20
13 5
14 -5
13 11
20 0
-4 18
-2 -2
-18...

output:

8.393071595900
16.453441243477
14.475640085236
19.043231368144
16.182932417451
19.043231368144
19.010576536590
3.305893553661
11.763187620795
14.667308360056
16.295525639797
7.617705510948
16.692652903019
25.870057685089
16.182932198760
20.084870431585
10.694511684541
19.295116007469
23.759261884935...

result:

ok 1681 numbers

Test #8:

score: 0
Accepted
time: 0ms
memory: 6120kb

input:

3 3 108
8
16
4
0 1
0 -1
-1 0
0 0
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10
0 11
0 12
0 13
0 14
0 15
0 16
0 17
0 18
0 19
0 0
0 -1
0 -2
0 -3
0 -4
0 -5
0 -6
0 -7
0 -8
0 -9
0 -10
0 -11
0 -12
0 -13
0 -14
0 -15
0 -16
0 -17
0 -18
0 -19
0 0
1 0
2 0
3 0
4 0
5 0
6 0
7 0
8 0
9 0
10 0
11 0
12 0
13 0
14 0
15 0
16...

output:

4.000000000000
3.000000000000
2.000000000000
1.000000000000
0.000000000000
1.000000000000
2.000000000000
1.000000000000
0.000000000000
1.000000000000
2.000000000000
3.000000000000
4.000000000000
3.000000000000
2.000000000000
1.000000000000
0.000000000000
1.000000000000
2.000000000000
3.000000000000
...

result:

ok 108 numbers

Test #9:

score: 0
Accepted
time: 3ms
memory: 8068kb

input:

3 3 1681
8
16
4
-1 0
0 1
0 -1
9 2
-17 -3
15 3
-19 -6
-6 -16
19 6
-12 -16
1 4
4 12
4 -15
-1 -17
5 7
12 13
19 -19
6 -16
-9 -19
6 -10
1 -20
18 17
-2 -20
13 -13
2 -7
13 14
-15 -7
7 -2
-3 4
-15 11
13 -15
20 -20
13 5
14 -5
13 11
20 0
-4 18
-2 -2
-18 7
6 -3
-9 -9
-8 -12
-16 20
-1 -13
14 20
-7 -14
13 -14
19...

output:

9.219544457293
3.162277660168
15.033296378373
6.708203932499
6.000000000000
19.104973174543
12.000000000000
1.000000000000
5.656854249492
4.123105625618
1.414213562373
5.099019513593
12.369316876853
19.235384061671
6.000000000000
9.486832980505
6.324555320337
4.123105625618
18.027756377320
4.4721359...

result:

ok 1681 numbers

Test #10:

score: 0
Accepted
time: 0ms
memory: 6140kb

input:

3 2 1681
16
8
4
0 1
0 -1
-1 -17
-18 -12
4 -6
12 17
-14 -11
-10 19
-19 -15
-15 -17
2 13
-8 -13
-18 7
-17 12
-20 16
3 12
-13 13
10 5
18 -9
-16 4
1 17
-19 -6
-17 -4
12 -18
-10 -17
-9 -20
13 6
11 0
4 5
2 -15
8 -12
1 9
17 -10
1 -13
-8 1
-12 11
5 0
20 -16
-5 8
-13 -2
7 12
-8 14
-4 9
10 -11
19 -3
-18 8
-4 ...

output:

1.414213562373
18.439088914586
4.472135955000
12.041594578792
14.317821063276
10.440306508911
19.026297590440
15.033296378373
3.605551275464
8.544003745318
18.027756377320
17.464249196573
20.000000000000
5.000000000000
13.341664064126
10.049875621121
18.027756377320
16.000000000000
1.414213562373
19...

result:

ok 1681 numbers

Test #11:

score: 0
Accepted
time: 3ms
memory: 8132kb

input:

3 2 1681
16
8
4
-1 -999001
0 1
13 -1
-7 19
19 -13
17 -1
-14 14
18 -9
10 -10
11 20
6 16
-16 7
14 -7
-3 4
7 -14
-20 2
14 -6
13 16
-16 -13
2 0
-8 20
-3 20
0 14
-18 1
-15 12
-3 -12
-13 -14
14 0
12 4
-14 9
-10 -9
20 15
-20 0
19 4
16 -8
3 -14
19 -15
-11 19
6 -9
-17 -5
-17 13
18 12
6 12
-16 -10
12 7
8 -6
-...

output:

13.341667965588
7.615773105864
19.235399881682
17.262680444705
14.142135623731
18.027764372991
10.198046879677
11.704699910720
6.000000000000
16.031219541881
14.035676835267
3.000000000000
7.280125289047
20.099751242242
14.142139587489
13.000000000000
16.278804854418
4.472135955000
8.944271909999
5....

result:

ok 1681 numbers

Test #12:

score: 0
Accepted
time: 0ms
memory: 8140kb

input:

3 2 1
1
2
4
0 1
0 -1
-7 0

output:

7.071067811865

result:

ok found '7.0710678', expected '7.0710678', error '0.0000000'

Test #13:

score: 0
Accepted
time: 1ms
memory: 8128kb

input:

3 2 1
1
2
4
0 1
-1 -999001
-7 0

output:

7.071066820926

result:

ok found '7.0710668', expected '7.0710668', error '0.0000000'

Test #14:

score: 0
Accepted
time: 1ms
memory: 8012kb

input:

4 1 36
8
1
2
4
0 1
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 -1
0 -2
0 -3
0 -4
0 -5
0 -6
0 -7
0 -8
0 -9
-1 0
-2 0
-3 0
-4 0
-5 0
-6 0
-7 0
-8 0
-9 0
1 0
2 0
3 0
4 0
5 0
6 0
7 0
8 0
9 0

output:

0.000000000000
0.000000000000
1.000000000000
0.000000000000
1.000000000000
2.000000000000
1.000000000000
0.000000000000
1.000000000000
2.000000000000
3.000000000000
4.000000000000
5.000000000000
6.000000000000
7.000000000000
8.000000000000
9.000000000000
10.000000000000
1.414213562373
2.236067977500...

result:

ok 36 numbers

Test #15:

score: 0
Accepted
time: 1ms
memory: 6024kb

input:

4 5 8
8
1
2
4
0 1
1 1
1 -1
-3 2
-2 -5
-4 0
-4 -1
-4 -2
-8 -1
-8 -2
-8 -3
-8 -4
-9 -3

output:

2.318273189507
3.147379239224
3.043003664557
5.601139657638
6.294758478447
6.553438496857
6.086007329113
7.480164533118

result:

ok 8 numbers

Test #16:

score: 0
Accepted
time: 164ms
memory: 14400kb

input:

99999 99999 99999
10
20
30
40
50
60
70
80
90
100
110
120
130
140
150
160
170
180
190
200
210
220
230
240
250
260
270
280
290
300
310
320
330
340
350
360
370
380
390
400
410
420
430
440
450
460
470
480
490
500
510
520
530
540
550
560
570
580
590
600
610
620
630
640
650
660
670
680
690
700
710
720
730...

output:

10.998865701869
14.525423018761
21.073102117794
31.843189113241
115.924895013616
49.991391054940
60.506629716442
69.958130039586
134.902308151242
90.172561431423
100.220151411668
110.154852885070
119.838138057650
169.259259924831
139.857713809972
149.903862612096
159.813034019318
169.924008912966
20...

result:

ok 99999 numbers

Test #17:

score: 0
Accepted
time: 153ms
memory: 13028kb

input:

99999 99999 99999
10
20
30
40
50
60
70
80
90
100
110
120
130
140
150
160
170
180
190
200
210
220
230
240
250
260
270
280
290
300
310
320
330
340
350
360
370
380
390
400
410
420
430
440
450
460
470
480
490
500
510
520
530
540
550
560
570
580
590
600
610
620
630
640
650
660
670
680
690
700
710
720
730...

output:

10.000000000000
15.295841308968
21.472081503159
30.839308519800
35.006555272524
50.931458107477
60.506619828998
70.363795442202
80.007038937116
90.056171321627
100.000633293052
110.050508279774
119.838128085721
129.885197989282
134.868076476159
149.833874636269
159.950469676917
169.923998940019
174....

result:

ok 99999 numbers

Test #18:

score: 0
Accepted
time: 156ms
memory: 13052kb

input:

99999 99999 99999
10
20
30
40
50
60
70
80
90
100
110
120
130
140
150
160
170
180
190
200
210
220
230
240
250
260
270
280
290
300
310
320
330
340
350
360
370
380
390
400
410
420
430
440
450
460
470
480
490
500
510
520
530
540
550
560
570
580
590
600
610
620
630
640
650
660
670
680
690
700
710
720
730...

output:

10.000000000000
11.793537328942
15.006851569379
30.316874089052
40.113906820859
50.140933717450
60.175584315259
70.363795442202
80.125534801392
89.856351459773
100.000633293052
109.955169614314
119.767282240876
129.812131979222
139.932670846876
149.713860056673
159.753646614700
169.738741224847
179....

result:

ok 99999 numbers

Test #19:

score: 0
Accepted
time: 0ms
memory: 6120kb

input:

3 3 1781
27448
700036
1565
727561 561893
946824 -149222
20811 -112456
-864128 96532
16 -3
-17 6
-20 20
-13 -9
3 1
6 6
-18 -10
-10 0
-4 2
19 -11
-3 18
9 -6
-14 -5
-17 1
-16 -7
20 6
20 10
0 -8
-15 20
-12 17
-8 -13
14 -8
-14 -4
20 -12
-11 0
-7 13
1 -4
-1 17
20 4
-17 12
-3 -4
8 3
-9 -9
-11 14
-12 14
-13...

output:

869958.248114477028
1548.728110911665
1574.070850191948
1568.855156609635
1558.582578139035
1562.014764098693
1556.584271779073
1558.564638007550
1566.850548158156
1566.948507823863
1544.539412209167
1556.455197783836
1555.182232268124
1562.699966582056
1569.163895394819
1561.121016860294
1545.52168...

result:

ok 1781 numbers

Test #20:

score: 0
Accepted
time: 3ms
memory: 8244kb

input:

2 2 1781
455464
989237
648422 -984508
-86934 -353141
15 -8
12 -16
-20 -3
-5 15
6 -9
19 -16
-16 5
6 6
3 16
-2 -4
-19 -5
-1 -5
5 -11
0 1
9 9
5 13
3 -15
10 -17
16 -20
2 15
9 -2
0 5
18 -6
-20 18
3 -8
-7 -2
13 -8
15 -13
885672 69814
893942 -786043
13 1
2 7
15 20
-12 -2
679345 587036
-20 8
-9 -9
0 17
15 -...

output:

455449.068343449268
455444.037305271020
455456.306609651365
455477.370048753801
455453.183515037643
455440.187062228564
455465.030764936295
455465.710642614693
455475.712201902759
455459.637885071163
455454.603568764054
455458.905910792935
455452.063287644240
455464.835137115675
455466.566020792641
...

result:

ok 1781 numbers

Test #21:

score: 0
Accepted
time: 0ms
memory: 8180kb

input:

4 4 1781
284368
639066
544427
453079
-473316 -385890
-403701 -456998
341400 289506
328542 749626
-11 0
15 -5
18 -15
4 18
-12 -15
-2 9
3 -20
-5 0
-5 8
14 -8
-247884 -376851
-14 -7
-2 19
18 5
4 -17
-17 10
-5 14
7 -6
4 0
13 -14
6 7
-17 19
2 20
-17 2
-18 -6
-14 -13
-2 17
16 -9
8 -13
12 5
850219 294605
2...

output:

284359.474486080755
284359.793732645165
284363.973878313380
284349.908226094150
284348.813509705709
284360.559810770268
284354.997431616939
284364.124745337409
284362.680004575523
284362.496790819510
64050.720210684543
284352.725997149013
284351.400949598872
284351.037832076894
284357.907791704172
2...

result:

ok 1781 numbers

Test #22:

score: 0
Accepted
time: 3ms
memory: 8220kb

input:

5 5 1781
855105
811761
393138
763609
395482
485837 -963055
-805058 420348
-996068 26540
957233 158478
40565 268210
19 -11
16 9
-8 -7
-15 -2
10 0
-19 -1
-5 4
-14 5
20 6
-10 -16
10 -1
-17 -6
16 -19
11 -20
-11 -20
7 -5
9 -16
7 -10
388718 -210265
-7 -12
1 6
-4 -7
-11 15
-4 -11
5 16
-1 -17
-15 9
-2 1
17 ...

output:

393119.621394643036
393120.744903681683
393130.189351588779
393123.058599690674
393128.134296897391
393119.033379073080
393131.716431363777
393123.275621858716
393117.288585386123
393128.219226072019
393128.297637329670
393121.165896118328
393113.829886579246
393115.189056911913
393125.098459256231
...

result:

ok 1781 numbers

Test #23:

score: 0
Accepted
time: 3ms
memory: 6016kb

input:

4 4 1781
360226
923659
843797
234702
385835 56098
-255808 -788591
-223435 302545
-943925 -181801
-1 -5
0 -16
7 -8
-13 0
-14 -17
0 17
-5 10
-14 -13
-4 -1
-14 -12
-19 0
-3 9
19 -20
-11 -13
746464 508236
-244133 857457
-9 -18
0 -6
8 12
-15 -18
-552127 -210744
-7 -1
-7 13
13 -18
-16 -18
3 10
8 11
2 0
18...

output:

234696.935415039392
234686.780762982758
234696.224052096833
234689.234624189150
234681.509833541262
234688.325222284388
234690.985530420934
234685.314701468771
234697.883062973619
234685.983333384647
234683.342920964380
234692.978097465064
234686.076394613978
234686.240279400459
396836.114925302041
...

result:

ok 1781 numbers

Test #24:

score: 0
Accepted
time: 3ms
memory: 6156kb

input:

2 2 1781
724290
427620
585285 -84915
-522957 846042
2 -4
5 -13
18 14
-5 -11
-18 4
9 12
6 9
-13 18
14 18
-2 19
17 6
17 10
5 -20
0 -7
-3 -7
-3 20
-7 11
-11 -14
7 -8
17 -5
-8 -19
-6 13
17 15
5 12
4 -18
-2 11
0 12
0 1
3 -8
11 6
-8 19
-10 11
-15 -8
-6 -18
20 -18
16 -16
16 2
-19 -10
-13 -12
-2 14
5 -18
-2...

output:

427617.446418637119
427613.185439975059
427604.196937802481
427623.368971969583
427607.133601538895
427612.816413233115
427615.354498480097
427597.853682650079
427608.729955872463
427602.786779337795
427604.037703262526
427604.612118823978
427612.180633454642
427618.994996686000
427621.963920057169
...

result:

ok 1781 numbers

Test #25:

score: 0
Accepted
time: 3ms
memory: 8144kb

input:

4 4 1781
509841
4372
912999
543071
445967 -716460
-693896 -395076
-734650 644244
-86759 -207195
-14 -17
1 -4
9 -5
-20 -7
12 4
0 17
0 19
2 -8
10 11
-10 1
-14 -6
-13 -1
-3 11
-8 -11
-10 11
-13 5
4 -14
-977857 62664
-16 0
5 -11
-19 -7
-1 -11
9 -11
-20 13
-1 8
-2 5
10 19
19 0
20 -9
-20 -20
6 -2
17 -6
-5...

output:

4350.916516885703
4368.075870665845
4363.002009875001
4351.157856369777
4369.071821570437
4360.810115602476
4359.496128618513
4364.152108232065
4372.291164919349
4363.808491637304
4356.865406077191
4360.211548211098
4362.496344194204
4358.764831637726
4357.229155238040
4358.931910459638
4358.0025208...

result:

ok 1781 numbers

Test #26:

score: 0
Accepted
time: 2ms
memory: 8192kb

input:

1 1 1781
730978
522802 -441174
-7 19
-5 -12
13 -4
12 17
-4 -16
-18 13
5 -6
-15 11
13 -10
1 -1
12 -14
-2 0
13 4
20 14
-3 18
-6 1
873868 299053
-13 7
-14 -5
5 20
12 4
-6 -4
-12 14
-1 -10
-9 10
-13 -12
-18 6
11 -4
13 13
11 14
-3 16
14 -4
13 0
14 19
-18 4
4 -19
19 -16
-6 11
-20 17
-3 13
-10 8
857606 -57...

output:

730995.603325437405
730974.082282885094
730965.485102324048
730979.792987545952
730970.738391330582
731000.140459052403
730970.309227254125
730996.557869047974
730961.615551213850
730976.590829609777
730959.800117169390
730979.528497912805
730970.644548550481
730971.744321334525
730991.901436980930
...

result:

ok 1781 numbers

Test #27:

score: 0
Accepted
time: 2ms
memory: 6084kb

input:

1 1 1781
372082
-541795 -869565
281973 459007
739644 385456
1 18
-14 16
-17 10
19 -13
-14 -20
19 -3
-6 -11
-17 5
-3 -10
-5 4
17 -3
-11 -16
-7 -19
-11 14
-8 5
8 0
-1 -3
11 -12
-9 13
-2 11
-11 -11
12 20
-9 -20
-12 -11
541236 905488
19 16
-9 -14
9 12
-18 17
3 20
16 8
-15 14
-20 17
-4 -4
14 -1
1 -2
-17 ...

output:

910776.206267791917
1169879.348474515136
372097.806162880734
372088.176890145056
372081.497990245698
372081.014669749246
372057.621846727037
372089.501738643216
372069.491004181677
372077.254180424789
372071.926200642949
372082.750912222604
372088.444027550984
372062.603239993099
372062.172322481172...

result:

ok 1781 numbers

Test #28:

score: 0
Accepted
time: 3ms
memory: 8188kb

input:

4 4 1781
8
4
5
6
-7 -2
5 10
1 5
-5 3
14 -16
-17 8
10 3
10 1
-17 -1
-7 -10
-8 5
-20 -12
20 11
16 5
7 -20
10 8
-3 12
17 4
1 16
2 -14
10 -13
-4 12
-4 -11
-11 2
1 -13
-5 -11
9 -20
1 15
5 15
-11 13
2 4
-19 2
10 12
-12 8
19 -1
-14 0
-5 6
2 -1
0 13
-5 -2
-9 8
11 9
-2 -15
-4 -8
0 0
-13 -8
-5 -20
64289 -8949...

output:

23.073767740705
10.858474455994
7.649399947186
8.504961407320
9.384559030415
7.832875423537
1.442652097559
15.734226393396
16.866311506196
12.607900073843
21.791970094608
6.477587843636
6.175927845593
13.788203719122
8.175175157812
14.163884242599
18.257900167049
6.948376998709
9.517544937156
4.6494...

result:

ok 1781 numbers

Test #29:

score: 0
Accepted
time: 3ms
memory: 8148kb

input:

2 2 1781
2
6
9 9
4 0
-6 -15
16 -2
-11 2
-955131 926039
-6 5
-9 0
-10 -1
13 -5
-10 12
0 -3
-13 -12
-18 -5
-2 -6
-8 10
13 13
2 16
13 6
-2 2
9 -8
-397859 -12783
-6 14
-7 -8
-1 15
-20 7
-16 -14
54141 265024
15 -19
-18 7
-3 14
-4 16
7 10
-15 15
19 5
0 5
-1 -5
-20 -15
-5 6
10 -19
-7 7
-17 7
19 -15
17 14
3...

output:

17.000000000000
10.198039027186
12.428026557854
1330347.149796098005
8.235801547193
10.509797530053
11.666734691944
8.602325267043
15.567374401308
3.605551275464
19.209372712299
20.446364563637
7.211102550928
12.741394968782
12.384776310850
11.969333116916
8.931945694498
3.464101615138
8.54400374531...

result:

ok 1781 numbers

Test #30:

score: 0
Accepted
time: 3ms
memory: 8164kb

input:

4 4 1781
9
2
19
5
-6 -1
-1 -8
-5 -2
-4 9
-3 20
18 -20
-20 -17
20 4
-7 12
12 -2
-2 -16
-9 15
13 11
-18 10
-14 -18
-5 8
20 14
-11 -4
2 16
-14 17
0 14
7 -6
5 3
5 -19
-8 4
-1 -12
18 6
-18 -1
-19 -7
13 6
-19 -3
-12 -2
8 15
4 1
0 -6
-12 -12
8 -13
20 -12
11 18
5 -9
-15 -20
19 -17
3 3
18 -15
14 -14
-8 -8
16...

output:

5.404020532762
20.388932589928
10.219556644124
20.925345696221
5.044131121937
12.248079206413
2.875484503403
2.688505513510
16.348661420395
12.647248742068
11.533394028769
1.363332334346
23.964433571521
2.724240537695
9.614741742517
6.293812489333
6.835165670830
7.690627985960
5.929336450028
7.35812...

result:

ok 1781 numbers

Test #31:

score: 0
Accepted
time: 2ms
memory: 8292kb

input:

1 1 1781
3
9 5
-8 -13
-5 1
12 2
12 -3
2 -13
-4 -1
11 -1
-18 -11
-160154 122064
8 1
6 -7
-1 -16
-19 -10
0 19
-6 -6
8 -11
5 20
-9 17
-12 11
-7 8
-16 5
-6 4
4 -9
-12 17
1 11
-8 15
2 6
10 17
-19 -15
4 17
-16 11
16 -17
-4 7
-20 11
-14 7
-8 -20
15 17
-7 16
338371 -987896
75680 -112362
-7 20
-17 1
3 20
-3 ...

output:

17.939891245093
7.636154837127
9.393240172864
10.382786181005
14.470323469725
7.063542469186
8.730376702242
24.092766949417
201368.836075977481
5.396905887552
9.106445034651
17.828815581801
24.470237133068
17.738001743309
11.399684533477
13.568083291459
18.694869081513
19.407960066178
17.46101057851...

result:

ok 1781 numbers

Test #32:

score: 0
Accepted
time: 0ms
memory: 8180kb

input:

1 1 1781
10
-8 7
5 1
2 -17
-14 -9
-13 -19
-18 11
14 -16
12 -12
18 2
15 2
-17 -20
-18 9
-13 5
18 -2
11 -4
-13 -17
18 5
13 -12
868693 773239
-17 -8
-10 18
-1 2
5 -2
-4 0
17 -19
-8 -7
-4 -4
197365 28813
-1 17
5 5
-18 10
-8 19
-13 -7
14 9
-7 5
7 -16
14 14
17 18
-7 1
6 -12
18 18
-8 -6
16 -20
-4 -10
-5 1
...

output:

13.714502444978
25.436089213233
16.876295650954
26.164132134780
11.366678326338
31.200047260154
26.956622796969
25.934290539356
22.987666782371
28.222788078910
10.749026025142
5.699087522521
26.930796393891
21.336523649953
24.212014084985
25.574932048935
27.689547603965
1162982.790501752635
17.39208...

result:

ok 1781 numbers

Test #33:

score: 0
Accepted
time: 0ms
memory: 6020kb

input:

1 1 1781
2
3 -8
-17 2
-5 9
19 -20
2 5
-15 -20
-5 -6
-11 0
-17 -13
17 2
3 -16
12 -12
17 17
13 10
12 13
-10 -12
12 -4
-1 0
0 -7
-8 -13
13 5
-20 14
8 -20
-14 1
-7 7
11 -18
18 -10
-15 -6
15 12
15 -17
10 11
-153064 -395673
19 -5
-10 13
3 5
-4 11
5 -12
2 15
-15 -15
-13 18
720298 994936
9 0
2 -15
-1 -17
13...

output:

18.120900293544
12.277227668503
25.756713381830
6.994111524609
23.982515970802
7.039216474162
11.851136292773
20.909023812565
16.751544388281
14.312981916307
15.172418208066
24.935797361358
17.093704927258
18.677130187407
14.734352280987
11.496295401678
2.530710130843
5.175208500927
14.126104661131
...

result:

ok 1781 numbers

Test #34:

score: 0
Accepted
time: 3ms
memory: 8292kb

input:

5 5 1781
1
2
5
6
7
-7 -4
2 7
-8 -6
4 -3
-7 6
-2 18
0 -9
7 -9
-17 8
20 -15
0 1
-19 -4
-978084 306093
0 19
4 1
4 12
-14 1
18 6
18 8
-9 0
-11 16
-17 0
-16 4
-4 -8
20 11
4 -16
1 1
-3 2
16 -17
13 10
17 11
11 -1
0 -12
-2 17
-7 6
4 20
-3 -2
-6 -7
-11 19
-9 -11
-7 -17
7 -6
2 -6
19 -19
12 -6
1 -9
-11 -13
1 -...

output:

11.932650869595
7.211102550928
5.000000000000
12.182294316343
18.000000000000
0.277402423779
12.933040773419
1024855.136242259527
12.419123557141
3.255764119220
5.663885030091
9.097817830700
16.056151469141
16.126983401557
4.538872557400
12.778779894090
11.461157540771
10.699635702053
4.123105625618...

result:

ok 1781 numbers

Test #35:

score: 0
Accepted
time: 0ms
memory: 8052kb

input:

1 1 1781
3
7 -6
-1 -12
-13 18
-13 14
18 10
13 -13
0 15
5 15
15 -6
-19 -8
-18 7
-19 13
-9 -8
-14 3
-4 -19
-19 -14
19 -18
-16 -19
2 -1
17 18
10 -18
15 9
-750503 54264
4 -19
-4 -16
4 -20
-7 -6
16 4
-14 -14
6 10
2 -17
-18 -20
-10 -5
9 13
16 14
15 -18
-9 -6
12 3
-15 20
-16 7
-13 -4
6 17
-6 3
10 -1
-20 -1...

output:

10.568753981684
25.129812639925
22.088197987948
19.749627068679
15.395332340873
17.104713491054
17.169552281294
13.350596104396
22.120516873341
22.166031461238
26.006095050953
12.796947706459
17.014458537400
18.166781274700
24.451764298294
23.176696895742
24.993967617269
0.992054701557
24.7959935250...

result:

ok 1781 numbers

Test #36:

score: 0
Accepted
time: 0ms
memory: 8168kb

input:

3 3 1781
1
5
6
1 0
2 4
-10 10
0 -2
1 14
12 18
19 16
2 -9
-15 8
0 -5
1 -19
-12 8
-10 -3
-12 19
390267 -598135
15 12
3 8
10 -9
-16 -7
-8 13
0 6
-10 4
-2 20
-12 9
-3 6
-158495 -417843
-14 -15
-14 17
-3 10
11 4
-18 14
-20 16
1 -18
13 -17
8 5
-6 -19
4 0
-953821 -473693
15 10
-7 -10
18 8
-7 -3
6 15
4 -6
1...

output:

2.236067977500
8.796002999432
15.697291772533
19.475761334388
9.055385138137
11.394671052405
5.099019513593
19.000000000000
8.619418339727
9.192525513532
16.672020795291
714191.239337195992
13.989425910523
2.652414037440
9.848857801796
16.267528012327
9.529380417477
2.708203932499
5.762470022539
15....

result:

ok 1781 numbers

Test #37:

score: 0
Accepted
time: 0ms
memory: 8132kb

input:

3 7 5
2
4
7
8 4
2 8
-1 5
-7 2
-4 -4
1 -8
6 -3
3 -1
8 1
2 6
-5 2
-1 -1

output:

0.977772290466
2.750120773895
0.846777708005
1.464071052924
0.585786437627

result:

ok 5 numbers

Test #38:

score: 0
Accepted
time: 44ms
memory: 13036kb

input:

99996 100000 100
524288
524290
262146
524291
786444
262156
262160
262169
262170
524314
786460
524317
786463
786464
786465
786473
262192
262195
262196
524341
524343
524347
786493
524351
524352
524354
524358
786504
262218
524363
786510
262227
524374
262234
262237
786526
524385
786531
262243
262244
262...

output:

6.462488165041
15.750796763274
53.678242235046
82.368444069289
13.983800968728
37.949624407792
19.417382739884
26436.954804314533
16.276546052013
17.455115463883
41.139742618270
10.886385126833
2.541277018553
43.124079192333
91.936832737985
29490.058645599194
25443.538643692991
26521.917535813303
25...

result:

ok 100 numbers

Test #39:

score: 0
Accepted
time: 219ms
memory: 12680kb

input:

100 100000 100000
519684
153097
817673
204302
50193
548881
600598
61977
360473
18978
943676
632382
60487
846418
325716
742485
16470
330336
240737
978021
385642
786539
871532
153708
561268
22644
795771
122496
468609
60545
617602
768142
385680
370839
482970
101019
67740
237725
915618
576686
501937
630...

output:

88245.972263364427
1395.006262689448
65837.716040132975
3799.085782635249
3433.758283839839
194.090692227504
7369.210725630206
265305.153138388996
8568.334302155690
4911.650769248928
54497.524328931962
3603.753680499834
3575.120818854331
159352.017849327967
3626.608676666186
100481.178871008800
7473...

result:

ok 100000 numbers

Test #40:

score: 0
Accepted
time: 234ms
memory: 11008kb

input:

99996 100 100000
262144
262145
262148
262156
786446
262163
262170
262171
524318
786463
262175
262176
524322
524323
524335
262193
262198
524343
262200
524352
786508
262220
786509
786516
524375
524378
262237
262238
262240
786528
786529
786530
524388
262245
786542
786546
262259
786548
262265
524410
524...

output:

5994.636172539137
5614.804600055700
18063.491359815860
48666.350136998648
29146.202153790196
1712.932520099852
166623.047461909970
37945.226124340094
14861.689749269408
52982.283561519565
2858.978120407571
13281.349540431642
2313.817285228569
9696.146442923935
24522.006430963105
915.755264890960
111...

result:

ok 100000 numbers

Test #41:

score: -100
Wrong Answer
time: 207ms
memory: 15088kb

input:

100000 100000 99999
786438
524295
262152
9
786447
524304
262161
18
786456
524313
262170
27
786465
524322
262179
36
786474
524331
262188
45
786483
524340
262197
54
786492
524349
262206
63
786501
524358
262215
72
786510
524367
262224
81
786519
524376
262233
90
786528
524385
262242
99
786537
524394
262...

output:

7.000000000000
7.000000000002
7.000000000002
7.000000000000
9.000000000000
9.000000000000
9.000000000000
9.000000000000
1.007620982403
2.000000000000
11.401762367722
11.401754250991
8.006305499964
9.000010282776
9.000000000000
20.124611797498
0.110770276275
2.000000000000
19.313217499422
19.31320791...

result:

wrong answer 16897th numbers differ - expected: '0.0001052', found: '0.0018987', error = '0.0017934'