QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#509542#3854. RadarwisniewskijAC ✓577ms11184kbC++202.7kb2024-08-08 15:54:282024-08-08 15:54:28

Judging History

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

  • [2024-08-08 15:54:28]
  • 评测
  • 测评结果:AC
  • 用时:577ms
  • 内存:11184kb
  • [2024-08-08 15:54:28]
  • 提交

answer

#include <bits/stdc++.h>
 
#define ndl '\n'
#define ll long long
#define INF 1000000007
#define st first
#define nd second
#define debug(x) cout << #x << ": " << x << ndl
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define all(x) (x).begin(), (x).end()
 
using namespace std;
 
typedef pair<long double, long double> point;
 
long double dist(point a, point b){
    long double y = b.nd - a.nd, x = b.st - a.st;
    return sqrt(y*y + x*x);
}
 
point pos(point angle, long double rad){
    long double dis = dist(angle, {0, 0});
    if(dis == 0) return angle;
    return {rad / dis * angle.st, rad / dis * angle.nd};
}

long double dot_prod(point a, point b){
    return a.st * b.st + a.nd * b.nd;
}
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int R, F, N; cin>>R>>F>>N;
    vector<long double> radii(R); for(auto &x: radii) cin>>x;
    vector<point> angles(F), points(N); 
    for(auto &[x, y]: angles) cin>>x>>y;
    for(auto &[x, y]: points) cin>>x>>y;
    sort(all(radii));
    sort(all(angles), [](point x, point y){return atan2(x.nd, x.st) < atan2(y.nd, y.st);});
 
    for(auto pt : points) {
        vector<vector<point>::iterator>loc_angles;
        {
            auto right_angle = upper_bound(all(angles), pt, [](point x, point y){return atan2(x.nd, x.st) < atan2(y.nd, y.st);});
            if(right_angle == angles.end()) right_angle = angles.begin();
            loc_angles.push_back(right_angle);
            if(points.size() > 1) {
                auto left_angle = right_angle;
                if(left_angle == angles.begin()) left_angle = angles.end();
                left_angle--;
                loc_angles.push_back(left_angle);
            }
        }
        vector<long double> loc_radii;
        for(auto l_angle : loc_angles){
            auto upper_radius = upper_bound(all(radii), dot_prod(*l_angle, pt) / dist(*l_angle, {0, 0}));
            if(upper_radius == radii.end()) {
                upper_radius--;
                loc_radii.push_back(*upper_radius);
            } else {
                loc_radii.push_back(*upper_radius);
                if(upper_radius != radii.begin()) {
                    upper_radius--;
                    loc_radii.push_back(*(upper_radius));
                }
            }
        }
 
        vector<long double> zzz;
        for(auto l_angle : loc_angles) {
            for(auto l_radius : loc_radii) {
                zzz.push_back(dist(pos(*l_angle, l_radius), pt));
            }
        }
        sort(all(zzz));
        cout<<setprecision(20)<<zzz[0]<<'\n';
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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.60529107291663996433
0.9777722904656049825
1.5518451054017895745
1.4142135623730950488

result:

ok 4 numbers

Test #2:

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

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.874985099257575043
15.874985099257575043
15.874985099257575043
15.874985099257575043
15.874985099257575043
15.874985099257575043
15.874985099257575043
15.874985099257575043
4.9296567010457233234
4.9296567010457233234
4.9296567010457233234
4.9296567010457233234
4.9296567010457233234
4.929656701045...

result:

ok 32 numbers

Test #3:

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

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.0553851381374166262
4.1231056256176605497
3.6055512754639892931
11.045361017187260775
15.297058540778354491
1.4142135623730950488
8.2462112512353210993
7
8.9442719099991587857
3
12.165525060596439378
5
5.0990195135927848299
11.180339887498948482
1.4142135623730950488
2
2
3
3.162277660168379332
8.2...

result:

ok 1681 numbers

Test #4:

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

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.777372119303551408
4.6315936825902144745
6.8956561009772562314
12.291422905366941493
6.5559640035805438938
4.2703042060470206408
4.3925360004476450668
6.3678258857452781101
6.5559640035805438938
2.9903163793705008662
10.187520359495127463
2.8336261665087121042
2.9770648313653493725
4.696779860161...

result:

ok 1681 numbers

Test #5:

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

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
4
4
4
5
5
5
5
1
1
1
1
8.0622577482985496528
8.0622577482985496528
8.0622577482985496528
8.0622577482985496528

result:

ok 16 numbers

Test #6:

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

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
2
4
8
16
32
64
128
256
512
1024
2048
4096
8192
16384
32768
65536
131072
262144
524288
1047.0004775548099052
2095.0002386634708926
4190.0001193317405441
8380.0000596658709089
16760.000029832935533
33520.000014916467777
67041.000007458122639
134083.00000372903351
268167.00000186450981
536334.0000009...

result:

ok 120 numbers

Test #7:

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

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.3930715958995580628
16.453441243476639316
14.475640085235757517
19.043231368144236875
16.182932417451168141
19.043231368144236875
19.010576536590186713
3.3058935536605719265
11.763187620795244258
14.667308360055634381
16.295525639797087843
7.6177055109476934556
16.692652903019119082
25.87005768508...

result:

ok 1681 numbers

Test #8:

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

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
3
2
1
0
1
2
1
0
1
2
3
4
3
2
1
0
1
2
3
4
3
2
1
0
1
2
1
0
1
2
3
4
3
2
1
0
1
2
3
4
4.1231056256176605497
4.4721359549995793928
5
5.6568542494923801951
6.4031242374328486864
7.2111025509279785863
8.0622577482985496528
8.9442719099991587857
9.8488578017961047216
10.770329614269008063
11.704699910719625...

result:

ok 108 numbers

Test #9:

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

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.21954445729288731
3.162277660168379332
15.033296378372908271
6.708203932499369089
6
19.104973174542800179
12
1
5.6568542494923801951
4.1231056256176605497
1.4142135623730950488
5.0990195135927848299
12.369316876852981649
19.235384061671344753
6
9.4868329805051379959
6.3245553203367586639
4.1231056...

result:

ok 1681 numbers

Test #10:

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

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.4142135623730950488
18.43908891458577462
4.4721359549995793928
12.04159457879229548
14.317821063276353155
10.44030650891055018
19.026297590440448064
15.033296378372908271
3.6055512754639892931
8.5440037453175311675
18.027756377319946466
17.464249196572980647
20
5
13.341664064126333713
10.049875621...

result:

ok 1681 numbers

Test #11:

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

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.34166796558825713
7.6157731058639082855
19.235399881681893625
17.262680444705100078
14.142135623730950488
18.02776437299067473
10.198046879676519698
11.704699910719625109
6
16.031219541881397365
14.035676835267185921
3
7.2801252890471757242
20.09975124224178054
14.142139587489013886
13
16.2788048...

result:

ok 1681 numbers

Test #12:

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

input:

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

output:

7.0710678118654752438

result:

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

Test #13:

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

input:

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

output:

7.0710668209259636453

result:

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

Test #14:

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

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
0
1
0
1
2
1
0
1
2
3
4
5
6
7
8
9
10
1.4142135623730950488
2.2360679774997896964
3.162277660168379332
4.1231056256176605497
5.0990195135927848299
6.0827625302982196889
7.0710678118654752438
8.0622577482985496528
9.0553851381374166262
1.4142135623730950488
2.2360679774997896964
3.162277660168379332
4...

result:

ok 36 numbers

Test #15:

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

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.3182731895074407177
3.147379239223550823
3.043003664556540048
5.6011396576375128377
6.294758478447101646
6.5534384968572901029
6.0860073291130800961
7.4801645331180126558

result:

ok 8 numbers

Test #16:

score: 0
Accepted
time: 493ms
memory: 11080kb

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.998865701868703821
14.525423018761116935
21.073102117794251114
31.843189113241067392
115.92489501361567265
49.99139105493989374
60.506629716441605045
69.958130039585846111
134.90230815124221229
90.172561431422949781
100.22015141166820756
110.15485288507004681
119.83813805765030346
169.25925992483...

result:

ok 99999 numbers

Test #17:

score: 0
Accepted
time: 540ms
memory: 10972kb

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
15.295841308968245689
21.472081503158729616
30.839308519800433951
35.006555272523729932
50.931458107477317221
60.506619828997750866
70.363795442201724634
80.007038937115761423
90.056171321627367113
100.0006332930519187
110.05050827977390913
119.83812808572126173
129.88519798928158457
134.86807647...

result:

ok 99999 numbers

Test #18:

score: 0
Accepted
time: 486ms
memory: 11136kb

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
11.793537328942145417
15.006851569378944748
30.316874089052133011
40.11390682085933378
50.140933717450125701
60.175584315259197835
70.363795442201724634
80.12553480139246511
89.856351459773306407
100.0006332930519187
109.95516961431412485
119.76728224087635847
129.8121319792217243
139.93267084687...

result:

ok 99999 numbers

Test #19:

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

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.24811447697999
1548.7281109116648894
1574.0708501919477855
1568.8551566096348494
1558.5825781390352968
1562.0147640986934643
1556.5842717790730851
1558.5646380075504674
1566.8505481581556196
1566.9485078238632854
1544.5394122091671812
1556.4551977838363305
1555.1822322681233687
1562.699966582...

result:

ok 1781 numbers

Test #20:

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

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.06834344927572
455444.03730527101507
455456.30660965142386
455477.37004875388126
455453.18351503767346
455440.18706222854115
455465.03076493636922
455465.71064261471324
455475.7122019027473
455459.6378850712025
455454.60356876410864
455458.90591079302342
455452.0632876442273
455464.8351371156...

result:

ok 1781 numbers

Test #21:

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

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.47448608079137
284359.79373264516065
284363.97387831339785
284349.90822609414985
284348.81350970568596
284360.5598107703062
284354.99743161695969
284364.12474533744
284362.68000457555721
284362.49679081947716
64050.72021068456192
284352.72599714900664
284351.4009495988802
284351.0378320768692...

result:

ok 1781 numbers

Test #22:

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

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.62139464304704
393120.74490368162557
393130.18935158874822
393123.05859969069977
393128.13429689734528
393119.03337907307321
393131.71643136373501
393123.27562185865878
393117.28858538611252
393128.21922607201861
393128.29763732964923
393121.16589611834183
393113.82988657925739
393115.1890569...

result:

ok 1781 numbers

Test #23:

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

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.93541503939305
234686.78076298277412
234696.22405209682229
234689.23462418915828
234681.50983354127025
234688.32522228438894
234690.98553042092612
234685.31470146878911
234697.88306297360172
234685.98333338463738
234683.34292096436887
234692.9780974650638
234686.07639461396518
234686.24027940...

result:

ok 1781 numbers

Test #24:

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

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.44641863714253
427613.18543997504449
427604.19693780246959
427623.36897196959308
427607.1336015388874
427612.81641323306874
427615.35449848004359
427597.85368265009956
427608.72995587243102
427602.78677933781205
427604.03770326254596
427604.61211882395716
427612.18063345464137
427618.99499668...

result:

ok 1781 numbers

Test #25:

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

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.916516885702594
4368.0758706658459465
4363.0020098750008639
4351.1578563697764648
4369.071821570437296
4360.8101156024760665
4359.496128618513616
4364.152108232064847
4372.2911649193489572
4363.8084916373034332
4356.8654060771913721
4360.2115482110986191
4362.4963441942034224
4358.7648316377256...

result:

ok 1781 numbers

Test #26:

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

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.60332543744079
730974.08228288513237
730965.48510232404414
730979.79298754594265
730970.7383913305809
731000.14045905244171
730970.30922725406464
730996.5578690479154
730961.61555121376404
730976.59082960971966
730959.80011716936718
730979.52849791274821
730970.64454855040645
730971.744321334...

result:

ok 1781 numbers

Test #27:

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

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.20626779191491
1169879.3484745152069
372097.80616288073145
372088.17689014503708
372081.49799024567321
372081.01466974922747
372057.62184672705715
372089.50173864315386
372069.49100418166657
372077.25418042474254
372071.9262006429544
372082.7509122226264
372088.44402755094944
372062.603239993...

result:

ok 1781 numbers

Test #28:

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

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.073767740704896487
10.858474455993557644
7.649399947186103796
8.5049614073201441709
9.3845590304146976248
7.8328754235368327815
1.4426520975592913568
15.73422639339602235
16.8663115061956645
12.607900073843284441
21.791970094608371818
6.4775878436357385505
6.175927845593418434
13.7882037191222564...

result:

ok 1781 numbers

Test #29:

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

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
10.19803902718556966
12.42802655785365269
1330347.1497960981136
8.2358015471929743494
10.509797530053360208
11.666734691943932736
8.602325267042626772
15.567374401308257216
3.6055512754639892931
19.20937271229854606
20.446364563637281782
7.2111025509279785863
12.74139496878217098
12.3847763108502...

result:

ok 1781 numbers

Test #30:

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

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.4040205327618385982
20.388932589928075251
10.219556644123653609
20.925345696220927549
5.0441311219366669191
12.248079206413251502
2.8754845034029006944
2.6885055135101258608
16.348661420395246077
12.647248742068138704
11.533394028768595541
1.3633323343457700006
23.964433571521224752
2.724240537695...

result:

ok 1781 numbers

Test #31:

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

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.939891245093073742
7.636154837126755141
9.3932401728639780374
10.382786181004820187
14.470323469725023735
7.0635424691856067898
8.7303767022420229703
24.092766949416909935
201368.83607597748509
5.3969058875520883821
9.1064450346514027781
17.828815581801218107
24.470237133067861433
17.738001743309...

result:

ok 1781 numbers

Test #32:

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

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.714502444978360254
25.436089213233453924
16.876295650953957655
26.164132134780405191
11.366678326338350136
31.200047260154135657
26.956622796969486575
25.934290539356099689
22.987666782370990034
28.222788078910077418
10.749026025142497569
5.6990875225214740175
26.930796393891078997
21.33652364995...

result:

ok 1781 numbers

Test #33:

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

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.120900293543999055
12.277227668502911502
25.756713381830350883
6.9941115246093807692
23.982515970802144773
7.039216474161791649
11.851136292773331971
20.909023812565241814
16.751544388280792812
14.312981916306624432
15.172418208065682707
24.935797361357514684
17.093704927258028824
18.677130187406...

result:

ok 1781 numbers

Test #34:

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

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.932650869594699871
7.2111025509279785863
5
12.182294316342506381
18
0.27740242377880129876
12.933040773418722985
1024855.136242259556
12.419123557141262187
3.2557641192199412775
5.6638850300909654952
9.097817830699935028
16.056151469141040711
16.12698340155680005
4.5388725573999256805
12.77877989...

result:

ok 1781 numbers

Test #35:

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

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.568753981684030403
25.129812639925068384
22.088197987948099936
19.749627068679197669
15.395332340873363582
17.10471349105377931
17.169552281293716611
13.350596104395804815
22.120516873340851569
22.166031461238222981
26.006095050953139145
12.796947706458736941
17.014458537399665012
18.166781274699...

result:

ok 1781 numbers

Test #36:

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

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.2360679774997896964
8.7960029994318804309
15.697291772532745624
19.475761334387565892
9.0553851381374166262
11.394671052404842602
5.0990195135927848299
19
8.619418339727373631
9.1925255135322672265
16.672020795290663291
714191.23933719601456
13.989425910523265086
2.6524140374401561073
9.8488578017...

result:

ok 1781 numbers

Test #37:

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

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.9777722904656049825
2.7501207738952139429
0.84677770800535227564
1.4640710529236702717
0.58578643762690495129

result:

ok 5 numbers

Test #38:

score: 0
Accepted
time: 259ms
memory: 8036kb

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.4624881650361801644
15.750796763306541999
53.678242235052187961
82.368444069275933851
13.983800968730744661
37.949624407787957283
19.417382739876458273
26436.954804314449561
16.276546052020481395
17.455115463849577625
41.139742618248653243
10.886385126879622242
2.5412770185836874072
43.12407919229...

result:

ok 100 numbers

Test #39:

score: 0
Accepted
time: 534ms
memory: 9600kb

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.972263364388581
1395.0062626894333256
65837.716040132988205
3799.0857826352513713
3433.7582838397871698
194.09069222749919449
7369.2107256302950842
265305.15313838888704
8568.3343021557302182
4911.6507692488024461
54497.524328931921278
3603.7536804998540947
3575.1208188543483755
159352.0178493...

result:

ok 100000 numbers

Test #40:

score: 0
Accepted
time: 228ms
memory: 7832kb

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.6361725391264805
5614.8046000557031108
18063.491359815856024
48666.350136998642622
29146.202153790202898
1712.9325200998175633
166623.04746190995208
37945.226124340107027
14861.689749269426658
52982.283561519559896
2858.9781204075785892
13281.349540431645431
2313.8172852285478438
9696.146442923...

result:

ok 100000 numbers

Test #41:

score: 0
Accepted
time: 553ms
memory: 10928kb

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
7.0000000000015873331
7.0000000000015873331
7
9
9
9
9
1.0076209824032362445
2
11.401762144590731662
11.401754250991379791
8.0063054999636754025
9.0000100001000009941
9
20.124611797498107267
0.11077027627483325208
2
19.313217235966209118
19.313207915827965838
16.012610999927350805
18.00002000020000...

result:

ok 99999 numbers

Test #42:

score: 0
Accepted
time: 565ms
memory: 11068kb

input:

95165 100000 100000
524289
524290
3
524291
5
524297
786442
524300
786447
262161
524325
41
786474
43
524340
262201
524347
524351
524352
68
786502
786505
75
262228
262230
89
262233
91
92
524382
95
786530
262250
109
524401
113
786547
114
262261
786550
262267
123
262271
127
524420
786565
524421
524424
2...

output:

4.8692960482461616813
10.547084101693446846
20.338245462779161692
11.047239177444609387
29307.643746329082036
8.6969391828850229099
12.982205241161078641
42.208825685683746494
18.284846836654092439
1.3245014228574849655
89248.113329288446756
10.698730258099449698
12.063924232591886113
82.45679089085...

result:

ok 100000 numbers

Test #43:

score: 0
Accepted
time: 552ms
memory: 11184kb

input:

95136 100000 100000
786432
524296
262156
524313
786458
262171
31
262178
38
262184
524332
524333
262197
262203
524348
786494
524350
262208
65
524359
262215
262217
524363
786515
524377
786524
96
97
262243
524389
524392
104
786538
107
786539
524396
110
117
262264
121
786559
128
262274
131
524422
262279...

output:

276808.61814054922075
10.735444517532323257
2.729671499338448994
305762.77751817021235
18.130777790201194909
24.254768209468661968
9.7506016302415298306
7.1811992373338052044
9.185528210606822638
51.864042051999212971
57.784192180242433402
304131.58640527212569
91.131096195772950293
21.5119422204931...

result:

ok 100000 numbers

Test #44:

score: 0
Accepted
time: 577ms
memory: 10984kb

input:

95116 100000 100000
786432
524298
13
262159
19
21
786455
28
524322
36
37
262182
262185
786475
786479
524340
786488
524350
262209
524354
786511
262224
786512
524369
524371
80
262229
524374
524376
262233
95
524384
262241
786531
262243
524390
786536
524394
524395
106
262255
112
262257
114
117
786551
78...

output:

2.0402331256157631625
17.842584580959037672
17.075114544418215785
11.280952583055351028
219404.30629707697805
27.077625533511525116
228139.77501133777402
14.189689595196943723
32.151684769750886333
13.958807259076533957
30.474901572722788143
352634.11064561914813
220634.7687600594181
67.337972452782...

result:

ok 100000 numbers