QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#243367#3854. RadarjeroenodbAC ✓176ms12468kbC++203.4kb2023-11-08 07:10:052023-11-08 07:10:06

Judging History

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

  • [2023-11-08 07:10:06]
  • 评测
  • 测评结果:AC
  • 用时:176ms
  • 内存:12468kb
  • [2023-11-08 07:10:05]
  • 提交

answer

#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef double ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
typedef complex<double> pt;
#define X real()
#define Y imag()
auto cross(pt u, pt v) {return (ll)u.X*v.Y-(ll)u.Y*v.X;}
auto sgn(ll a) {return a==0?0:(a>0?1:-1);}
auto ccw(pt p1, pt p2, pt p3) {auto u = p2-p1, v = p3-p2;return cross(u,v);}
auto in(pt p1, pt p2) {return (ll)p1.X*p2.X+(ll)p1.Y*p2.Y;}
// auto norm2(pt p) {return (ll)p.X*p.X+(ll)p.Y*p.Y;}
bool comp(const pt& a, const pt& b) { return a.X<b.X or (a.X==b.X and a.Y < b.Y);}
void read(pt& p) {
    int a,b; cin >> a >> b;
    p = {a,b};
}
bool lexo(pt a, pt b) {
    return a.X<b.X or (a.X==b.X and a.Y > b.Y);
}
pt o = {};
bool polarcomp(const pt& a, const pt& b) {
    bool lex1 = lexo(o,a), lex2 = lexo(o,b);
    if(lex1!=lex2) return lex1<lex2;
    return ccw(o,a,b)>0;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int R,f,n;
    cin >> R >> f >> n;
    vi r(R);
    for(auto& i : r) cin >> i;
    sort(all(r));
    vector<pair<pt,int>> pts;
    for(int i=0;i<f;++i) {
        pt p;
        read(p);
        pts.push_back({p,-1});
    }
    vector<double> d(n,INFINITY);
    for(int i=0;i<n;++i) {
        pt p;
        read(p);
        if(norm(p)==0) {
            d[i]=r[0];
        } else pts.push_back({p,i});
    }
    sort(all(pts),[&](auto i, auto j) {
        return polarcomp(i.first,j.first);
    });
    for(auto& [p,id] : pts) {
        if(id==-1) p/=abs(p);
    }
    
    for(int rep=0;rep<2;++rep) {
        {
            int i=0;
            while(pts[i].second!=-1) ++i;
            rotate(pts.begin(),i+all(pts));
        }
        
        auto updateAns = [&](pt p, int id, pt vec) {
            int lo=0,hi=R-1;
            auto mydist = [&](int i) {
                return norm(p-vec*double(r[i]));
            };
            while(lo<hi) {
                int mid = (lo+hi)/2;
                if(mydist(mid)>mydist(mid+1)) {
                    lo = mid+1;
                } else {
                    hi = mid;
                }
            }
            d[id] = min(d[id],sqrt(mydist(lo)));
        };
        const int M = 2;
        array<pt,M> last;
        for(int i=0;i<M;++i) {
            for(auto [p,id] : pts) {
                if(id==-1) {
                    copy(last.begin()+1,last.end(),last.begin());
                    last[M-1] = p/abs(p);
                }
            }
        }
        for(auto [p,id] : pts) {
            if(id==-1) {
                copy(last.begin()+1,last.end(),last.begin());
                last[M-1] = p;
            } else {
                for(auto& i : last) {
                    updateAns(p,id,i);
                }

            }
        }
        reverse(all(pts));
    }
    for(auto ans : d) {
        cout << setprecision(15) << ans << '\n';
    }


}

詳細信息

Test #1:

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

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.60529107291664
0.977772290465605
1.55184510540179
1.4142135623731

result:

ok 4 numbers

Test #2:

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

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.8749850992576
15.8749850992576
15.8749850992576
15.8749850992576
15.8749850992576
15.8749850992576
15.8749850992576
15.8749850992576
4.92965670104572
4.92965670104572
4.92965670104572
4.92965670104572
4.92965670104572
4.92965670104572
4.92965670104572
4.92965670104572
2
2
2
2
0.0710678118654765
0...

result:

ok 32 numbers

Test #3:

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

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.05538513813742
4.12310562561766
3.60555127546399
11.0453610171873
15.2970585407784
1.4142135623731
8.24621125123532
7
8.94427190999916
3
12.1655250605964
5
5.09901951359278
11.1803398874989
1.4142135623731
2
2
3
3.16227766016838
8.24621125123532
4.47213595499958
5
8.54400374531753
9
19.41648783894...

result:

ok 1681 numbers

Test #4:

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

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.7773721193035
4.63159368259021
6.89565610097726
12.2914229053669
6.55596400358054
4.27030420604702
4.39253600044765
6.36782588574528
6.55596400358054
2.9903163793705
10.1875203594951
2.83362616650871
2.97706483136535
4.69677986016195
4.35223988869312
11.3284558097968
3.38403014770991
1.8364593657...

result:

ok 1681 numbers

Test #5:

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

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.06225774829855
8.06225774829855
8.06225774829855
8.06225774829855

result:

ok 16 numbers

Test #6:

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

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.00047755481
2095.00023866347
4190.00011933174
8380.00005966587
16760.0000298329
33520.0000149165
67041.0000074581
134083.000003729
268167.000001865
536334.000000932
1
2
4
8
16
32
64
128
256
512
1024
2048
409...

result:

ok 120 numbers

Test #7:

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

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.39307159589956
16.4534412434766
14.4756400852358
19.0432313681442
16.1829324174512
19.0432313681442
19.0105765365902
3.30589355366057
11.7631876207952
14.6673083600556
16.2955256397971
7.61770551094769
16.6926529030191
25.8700576850889
16.1829321987597
20.0848704315849
10.6945116845406
19.29511600...

result:

ok 1681 numbers

Test #8:

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

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.12310562561766
4.47213595499958
5
5.65685424949238
6.40312423743285
7.21110255092798
8.06225774829855
8.94427190999916
9.8488578017961
10.770329614269
11.7046999107196
12.6491106406735
13.6014705087354
14.56021977856...

result:

ok 108 numbers

Test #9:

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

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.21954445729289
3.16227766016838
15.0332963783729
6.70820393249937
6
19.1049731745428
12
1
5.65685424949238
4.12310562561766
1.4142135623731
5.09901951359278
12.369316876853
19.2353840616713
6
9.48683298050514
6.32455532033676
4.12310562561766
18.0277563773199
4.47213595499958
13.3416640641263
2.23...

result:

ok 1681 numbers

Test #10:

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

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.4142135623731
18.4390889145858
4.47213595499958
12.0415945787923
14.3178210632764
10.4403065089106
19.0262975904404
15.0332963783729
3.60555127546399
8.54400374531753
18.0277563773199
17.464249196573
20
5
13.3416640641263
10.0498756211209
18.0277563773199
16
1.4142135623731
19.1049731745428
17
12....

result:

ok 1681 numbers

Test #11:

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

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.3416679655883
7.61577310586391
19.2353998816819
17.2626804447051
14.142135623731
18.0277643729907
10.1980468796765
11.7046999107196
6
16.0312195418814
14.0356768352672
3
7.28012528904718
20.0997512422418
14.142139587489
13
16.2788048544176
4.47213595499958
8.94427190999916
5
2
18.2482875908947
15...

result:

ok 1681 numbers

Test #12:

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

input:

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

output:

7.07106781186548

result:

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

Test #13:

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

input:

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

output:

7.07106682092596

result:

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

Test #14:

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

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.4142135623731
2.23606797749979
3.16227766016838
4.12310562561766
5.09901951359278
6.08276253029822
7.07106781186548
8.06225774829855
9.05538513813742
1.4142135623731
2.23606797749979
3.16227766016838
4.12310562561766
5.09901951359278
6.08276253029822
7.07106781...

result:

ok 36 numbers

Test #15:

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

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.31827318950744
3.14737923922355
3.04300366455654
5.60113965763751
6.2947584784471
6.55343849685729
6.08600732911308
7.48016453311801

result:

ok 8 numbers

Test #16:

score: 0
Accepted
time: 155ms
memory: 11356kb

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.9988657018687
14.5254230187611
21.0731021177942
31.8431891132411
115.924895013616
49.9913910549399
60.5066297164416
69.9581300395859
134.902308151242
90.1725614314229
100.220151411668
110.15485288507
119.83813805765
169.259259924831
139.857713809972
149.903862612096
159.813034019318
169.924008912...

result:

ok 99999 numbers

Test #17:

score: 0
Accepted
time: 160ms
memory: 11016kb

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.2958413089682
21.4720815031587
30.8393085198004
35.0065552725237
50.9314581074773
60.5066198289977
70.3637954422017
80.0070389371158
90.0561713216274
100.000633293052
110.050508279774
119.838128085721
129.885197989282
134.868076476159
149.833874636269
159.950469676917
169.923998940019
174.7854...

result:

ok 99999 numbers

Test #18:

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

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.7935373289421
15.0068515693789
30.3168740890521
40.1139068208593
50.1409337174501
60.1755843152592
70.3637954422017
80.1255348013925
89.8563514597733
100.000633293052
109.955169614314
119.767282240876
129.812131979222
139.932670846876
149.713860056673
159.7536466147
169.738741224847
179.900467...

result:

ok 99999 numbers

Test #19:

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

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.248114477
1548.72811091167
1574.07085019195
1568.85515660963
1558.58257813904
1562.01476409869
1556.58427177907
1558.56463800755
1566.85054815816
1566.94850782386
1544.53941220917
1556.45519778384
1555.18223226812
1562.69996658206
1569.16389539482
1561.12101686029
1545.52168009524
1543.064681...

result:

ok 1781 numbers

Test #20:

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

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.068343449
455444.037305271
455456.306609651
455477.370048754
455453.183515038
455440.187062229
455465.030764936
455465.710642615
455475.712201903
455459.637885071
455454.603568764
455458.905910793
455452.063287644
455464.835137116
455466.566020793
455472.106707416
455449.822857526
455444.3022...

result:

ok 1781 numbers

Test #21:

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

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.474486081
284359.793732645
284363.973878313
284349.908226094
284348.813509706
284360.55981077
284354.997431617
284364.124745337
284362.680004576
284362.49679082
64050.7202106845
284352.725997149
284351.400949599
284351.037832077
284357.907791704
284361.143620402
284357.184700945
284366.541860...

result:

ok 1781 numbers

Test #22:

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

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.621394643
393120.744903682
393130.189351589
393123.058599691
393128.134296897
393119.033379073
393131.716431364
393123.275621859
393117.288585386
393128.219226072
393128.29763733
393121.165896118
393113.829886579
393115.189056912
393125.098459256
393130.38305493
393119.661164347
393125.918921...

result:

ok 1781 numbers

Test #23:

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

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.935415039
234686.780762983
234696.224052097
234689.234624189
234681.509833541
234688.325222284
234690.985530421
234685.314701469
234697.883062974
234685.983333385
234683.342920964
234692.978097465
234686.076394614
234686.2402794
396836.114925302
313138.097860579
234682.101298
234696.292773948...

result:

ok 1781 numbers

Test #24:

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

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.446418637
427613.185439975
427604.196937802
427623.36897197
427607.133601539
427612.816413233
427615.35449848
427597.85368265
427608.729955872
427602.786779338
427604.037703263
427604.612118824
427612.180633455
427618.994996686
427621.963920057
427601.410370603
427606.962712487
427626.1253337...

result:

ok 1781 numbers

Test #25:

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

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.9165168857
4368.07587066585
4363.002009875
4351.15785636978
4369.07182157044
4360.81011560248
4359.49612861851
4364.15210823207
4372.29116491935
4363.8084916373
4356.86540607719
4360.2115482111
4362.4963441942
4358.76483163773
4357.22915523804
4358.93191045964
4358.002520899
546468.250839959
43...

result:

ok 1781 numbers

Test #26:

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

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.603325437
730974.082282885
730965.485102324
730979.792987546
730970.738391331
731000.140459052
730970.309227254
730996.557869048
730961.615551214
730976.59082961
730959.800117169
730979.528497913
730970.64454855
730971.744321335
730991.901436981
730983.230418933
832464.818839349
730992.449689...

result:

ok 1781 numbers

Test #27:

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

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.206267792
1169879.34847452
372097.806162881
372088.176890145
372081.497990246
372081.014669749
372057.621846727
372089.501738643
372069.491004182
372077.254180425
372071.926200643
372082.750912223
372088.444027551
372062.603239993
372062.172322481
372088.065690161
372082.013262062
372086.2305...

result:

ok 1781 numbers

Test #28:

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

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.0737677407049
10.8584744559936
7.6493999471861
8.50496140732014
9.3845590304147
7.83287542353683
1.44265209755929
15.734226393396
16.8663115061957
12.6079000738433
21.7919700946084
6.47758784363574
6.17592784559342
13.7882037191223
8.17517515781243
14.1638842425991
18.2579001670493
6.948376998708...

result:

ok 1781 numbers

Test #29:

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

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.1980390271856
12.4280265578537
1330347.1497961
8.23580154719297
10.5097975300534
11.6667346919439
8.60232526704263
15.5673744013083
3.60555127546399
19.2093727122985
20.4463645636373
7.21110255092798
12.7413949687822
12.3847763108502
11.9693331169162
8.93194569449832
3.46410161513775
8.5440037...

result:

ok 1781 numbers

Test #30:

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

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.40402053276184
20.3889325899281
10.2195566441237
20.9253456962209
5.04413112193667
12.2480792064133
2.8754845034029
2.68850551351013
16.3486614203952
12.6472487420681
11.5333940287686
1.36333233434577
23.9644335715212
2.72424053769545
9.61474174251654
6.29381248933266
6.83516567083017
7.6906279859...

result:

ok 1781 numbers

Test #31:

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

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.9398912450931
7.63615483712676
9.39324017286398
10.3827861810048
14.470323469725
7.06354246918561
8.73037670224202
24.0927669494169
201368.836075977
5.39690588755209
9.1064450346514
17.8288155818012
24.4702371330679
17.7380017433091
11.3996845334775
13.5680832914585
18.6948690815132
19.4079600661...

result:

ok 1781 numbers

Test #32:

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

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.7145024449784
25.4360892132335
16.876295650954
26.1641321347804
11.3666783263384
31.2000472601541
26.9566227969695
25.9342905393561
22.987666782371
28.2227880789101
10.7490260251425
5.69908752252147
26.9307963938911
21.3365236499528
24.2120140849849
25.5749320489346
27.6895476039648
1162982.79050...

result:

ok 1781 numbers

Test #33:

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

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.2772276685029
25.7567133818304
6.99411152460938
23.9825159708021
7.03921647416179
11.8511362927733
20.9090238125652
16.7515443882808
14.3129819163066
15.1724182080657
24.9357973613575
17.093704927258
18.6771301874069
14.7343522809868
11.4962954016784
2.53071013084343
5.17520850092...

result:

ok 1781 numbers

Test #34:

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

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.9326508695947
7.21110255092798
5
12.1822943163425
18
0.277402423778801
12.9330407734187
1024855.13624226
12.4191235571413
3.25576411921994
5.66388503009097
9.09781783069993
16.056151469141
16.1269834015568
4.53887255739993
12.7787798940903
11.4611575407713
10.6996357020526
4.12310562561766
18.574...

result:

ok 1781 numbers

Test #35:

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

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.1298126399251
22.0881979879481
19.7496270686792
15.3953323408734
17.1047134910538
17.1695522812937
13.3505961043958
22.1205168733409
22.1660314612382
26.0060950509531
12.7969477064587
17.0144585373997
18.1667812746999
24.4517642982944
23.1766968957423
24.9939676172689
0.9920547015...

result:

ok 1781 numbers

Test #36:

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

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.23606797749979
8.79600299943188
15.6972917725327
19.4757613343876
9.05538513813742
11.3946710524048
5.09901951359278
19
8.61941833972737
9.19252551353227
16.6720207952907
714191.239337196
13.9894259105233
2.65241403744016
9.8488578017961
16.2675280123273
9.52938041747679
2.70820393249937
5.7624700...

result:

ok 1781 numbers

Test #37:

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

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.977772290465605
2.75012077389521
0.846777708005352
1.46407105292367
0.585786437626905

result:

ok 5 numbers

Test #38:

score: 0
Accepted
time: 29ms
memory: 7420kb

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.46248816504137
15.750796763274
53.6782422350459
82.3684440692894
13.9838009687283
37.9496244077922
19.4173827398841
26436.9548043145
16.276546052013
17.4551154638826
41.1397426182705
10.8863851268335
2.54127701855253
43.1240791923326
91.9368327379855
29490.0586455992
25443.538643693
26521.91753581...

result:

ok 100 numbers

Test #39:

score: 0
Accepted
time: 119ms
memory: 11860kb

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.9722633644
1395.00626268945
65837.716040133
3799.08578263525
3433.75828383984
194.090692227504
7369.21072563021
265305.153138389
8568.33430215569
4911.65076924893
54497.524328932
3603.75368049983
3575.12081885433
159352.017849328
3626.60867666619
100481.178871009
74738.6123827259
2868.23912531...

result:

ok 100000 numbers

Test #40:

score: 0
Accepted
time: 154ms
memory: 8640kb

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.63617253914
5614.8046000557
18063.4913598159
48666.3501369986
29146.2021537902
1712.93252009985
166623.04746191
37945.2261243401
14861.6897492694
52982.2835615196
2858.97812040757
13281.3495404316
2313.81728522857
9696.14644292393
24522.0064309631
915.75526489096
11130.9887613381
94958.55636576...

result:

ok 100000 numbers

Test #41:

score: 0
Accepted
time: 148ms
memory: 12180kb

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.00000000000159
7.00000000000159
7
9
9
9
9
1.00762098240324
2
11.4017621445907
11.4017542509914
8.00630549996368
9.0000100001
9
20.1246117974981
0.110770276274835
2
19.3132172359662
19.313207915828
16.0126109999274
18.0000200002
18
32.4499614791759
0.504026693019544
2
27.8926610420272
27.89265136...

result:

ok 99999 numbers

Test #42:

score: 0
Accepted
time: 168ms
memory: 11596kb

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.86929604826276
10.5470841016719
20.3382454627769
11.0472391774514
29307.643746329
8.69693918288829
12.9822052411236
42.2088256856744
18.2848468366884
1.32450142285044
89248.1133292884
10.698730258052
12.0639242325825
82.4567908908352
0.27392945052518
4.08210215699565
229619.295449568
173821.018307...

result:

ok 100000 numbers

Test #43:

score: 0
Accepted
time: 176ms
memory: 11892kb

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.618140549
10.735444517544
2.7296714993175
305762.77751817
18.1307777901915
24.2547682094326
9.7506016302334
7.18119923728269
9.18552821058237
51.8640420519879
57.7841921802587
304131.586405272
91.1310961957866
21.511942220468
5.61048998178482
13.2966428264315
149597.310050029
6.0074650056555
...

result:

ok 100000 numbers

Test #44:

score: 0
Accepted
time: 173ms
memory: 12468kb

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.04023312568418
17.8425845809888
17.075114544421
11.2809525830567
219404.306297077
27.0776255335046
228139.775011338
14.1896895951867
32.1516847697745
13.9588072590661
30.4749015727353
352634.110645619
220634.768760059
67.3379724527796
65.6108846852401
7.95464692707641
8.8804691929455
24.5766460888...

result:

ok 100000 numbers