QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#73257#3854. Radarricky0129AC ✓129ms11800kbC++174.7kb2023-01-23 09:06:132023-09-24 14:36:46

Judging History

你现在查看的是测评时间为 2023-09-24 14:36:46 的历史记录

  • [2023-09-24 14:47:32]
  • 管理员手动重测本题所有提交记录
  • 测评结果:AC
  • 用时:133ms
  • 内存:12952kb
  • [2023-09-24 14:36:46]
  • 管理员手动重测该提交记录
  • 测评结果:0
  • 用时:129ms
  • 内存:11800kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-23 09:06:16]
  • 评测
  • 测评结果:100
  • 用时:219ms
  • 内存:11748kb
  • [2023-01-23 09:06:13]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vll vector<ll>
#define FOR(i,n) for(int i=0;i<n;i++)
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define f first
#define s second

const int MOD = (int)1e9+7;

template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
template<class T>
struct Point {
	typedef Point P;
	T x, y;
	explicit Point(T x=0, T y=0) : x(x), y(y) {}
	bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); }
	bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); }
	P operator+(P p) const { return P(x+p.x, y+p.y); }
	P operator-(P p) const { return P(x-p.x, y-p.y); }
	P operator*(T d) const { return P(x*d, y*d); }
	P operator/(T d) const { return P(x/d, y/d); }
	T dot(P p) const { return x*p.x + y*p.y; }
	T cross(P p) const { return x*p.y - y*p.x; }
	T cross(P a, P b) const { return (a-*this).cross(b-*this); }
	T dist2() const { return x*x + y*y; }
	long double dist() const { return sqrt((long double)dist2()); }
	P unit() const { return *this/dist(); } // makes dist()=1
};
struct Angle {
	int x, y;
	int t;
        int type;
        int idx;
	Angle(int x=0, int y=0, int t=0) : x(x), y(y), t(t) {}
	Angle operator-(Angle b) const { return {x-b.x, y-b.y, t}; }
	int half() const {
		return y < 0 || (y == 0 && x < 0);
	}
	Angle t90() const { return {-y, x, t + (half() && x >= 0)}; }
	Angle t180() const { return {-x, -y, t + half()}; }
	Angle t360() const { return {x, y, t + 1}; }
};

long double eps=1e-11;
template<class F>
long double ternSearch(int a, int b, F f, Angle line, Angle point) {
        int iter = 0;
        /*
        int best = a;
    
        for(int i=a;i<=b;i++) if(f(line,point,i)<f(line,point,best)){
            printf("%.8Lf\n",f(line,point,i));
            best = i;
        }
        return f(line,point,best);
        */
        
	while (b - a >= 5) {
		int mid = (a + b) / 2;
                assert( abs(f(line,point,mid)-f(line,point,mid+1))>=eps );
		if (-f(line,point,mid) < -f(line,point,mid+1)) a = mid; // (A)
		else b = mid+1;
	}
	rep(i,a+1,b+1) if (-f(line,point,a) < -f(line,point,i)) a = i; // (B)
        return f(line,point,a);
}
typedef Point<long double> P;
int main()
{
    int r,f,n;
    scanf("%d%d%d",&r,&f,&n);
    vi dist(r);
    FOR(i,r)
        scanf("%d",&dist[i]);
    sort(dist.begin(),dist.end());
    vector<Angle> v(f+n);
    FOR(i,f){
        scanf("%d%d",&v[i].x,&v[i].y);
        v[i].type = 0;
        /*
        v[2*i+1].x = -v[2*i].y;
        v[2*i+1].y = -v[2*i].x;
        v[2*i+1].type = 0;
        */
    }
    FOR(i,n){
        scanf("%d%d",&v[i+f].x,&v[i+f].y);
        v[i+f].type = 1;
        v[i+f].idx = i;
    }
    auto F = [&](Angle& line, Angle& point,int i){
        P p1(line.x,line.y);
        p1 = p1.unit();
        p1=p1*dist[i];
        return (p1-P(point.x,point.y)).dist();
    };
    sort(v.begin(),v.end(),[](Angle a, Angle b){
    return make_tuple(a.t, a.half(), a.y * (ll)b.x) <
               make_tuple(b.t, b.half(), a.x * (ll)b.y);

    });
    int prev = -1, next = -1;
    vector<long double> ans(n,-1);
    FOR(i,f+n){
        if(v[i].type==0){
            prev = i;
        }
    }
    vector<Angle> q;
    FOR(i,f+n){
        if(v[i].type==1) q.push_back(v[i]); 
        else{
            if(next==-1) next = i;
            else{
                prev = next;
                next = i;
            }
            while(sz(q)){
                Angle ff = q.back();
                q.pop_back();
                //cout<<v[prev].x<<" "<<v[prev].y<<" "<<ff.x<<" "<<ff.y<<endl;
                //cout<<v[next].x<<" "<<v[next].y<<" "<<ff.x<<" "<<ff.y<<endl;
                long double a1 = ternSearch(0,r-1,F,v[prev],ff);
                long double a2 = ternSearch(0,r-1,F,v[next],ff);
                ans[ff.idx] = min(a1,a2);
            }
        }
    }
    int init = 0;
    FOR(i,f+n){
        if(v[i].type==0){
            init = i;
            break;
        }
    }
    while(sz(q)){
        Angle ff = q.back();
        q.pop_back();
        //cout<<v[prev].x<<" "<<v[prev].y<<" "<<ff.x<<" "<<ff.y<<endl;
        //cout<<v[next].x<<" "<<v[next].y<<" "<<ff.x<<" "<<ff.y<<endl;
        long double a1 = ternSearch(0,r-1,F,v[prev],ff);
        long double a2 = ternSearch(0,r-1,F,v[next],ff);
        long double a3 = ternSearch(0,r-1,F,v[init],ff);
        ans[ff.idx] = min(a1,a2);
        ans[ff.idx] = min(ans[ff.idx],a3);
    }
    FOR(i,n){
        printf("%.8Lf\n",ans[i]);
    }

    
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3732kb

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.60529107
0.97777229
1.55184511
1.41421356

result:

ok 4 numbers

Test #2:

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

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.87498510
15.87498510
15.87498510
15.87498510
15.87498510
15.87498510
15.87498510
15.87498510
4.92965670
4.92965670
4.92965670
4.92965670
4.92965670
4.92965670
4.92965670
4.92965670
2.00000000
2.00000000
2.00000000
2.00000000
0.07106781
0.07106781
0.07106781
0.07106781
2.00000000
2.00000000
2.0000...

result:

ok 32 numbers

Test #3:

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

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.05538514
4.12310563
3.60555128
11.04536102
15.29705854
1.41421356
8.24621125
7.00000000
8.94427191
3.00000000
12.16552506
5.00000000
5.09901951
11.18033989
1.41421356
2.00000000
2.00000000
3.00000000
3.16227766
8.24621125
4.47213595
5.00000000
8.54400375
9.00000000
19.41648784
2.23606798
3.6055512...

result:

ok 1681 numbers

Test #4:

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

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.77737212
4.63159368
6.89565610
12.29142291
6.55596400
4.27030421
4.39253600
6.36782589
6.55596400
2.99031638
10.18752036
2.83362617
2.97706483
4.69677986
4.35223989
11.32845581
3.38403015
1.83645937
2.94725152
7.63513190
9.09218467
8.02697478
5.72755681
10.73846242
2.67892208
7.86903994
2.6606535...

result:

ok 1681 numbers

Test #5:

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

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.00000000
4.00000000
4.00000000
4.00000000
5.00000000
5.00000000
5.00000000
5.00000000
1.00000000
1.00000000
1.00000000
1.00000000
8.06225775
8.06225775
8.06225775
8.06225775

result:

ok 16 numbers

Test #6:

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

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.00000000
2.00000000
4.00000000
8.00000000
16.00000000
32.00000000
64.00000000
128.00000000
256.00000000
512.00000000
1024.00000000
2048.00000000
4096.00000000
8192.00000000
16384.00000000
32768.00000000
65536.00000000
131072.00000000
262144.00000000
524288.00000000
1047.00047755
2095.00023866
4190...

result:

ok 120 numbers

Test #7:

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

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.39307160
16.45344124
14.47564009
19.04323137
16.18293242
19.04323137
19.01057654
3.30589355
11.76318762
14.66730836
16.29552564
7.61770551
16.69265290
25.87005769
16.18293220
20.08487043
10.69451168
19.29511601
23.75926188
19.33616564
17.38477631
6.42433455
18.10569617
15.61689155
6.42433510
4.012...

result:

ok 1681 numbers

Test #8:

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

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.00000000
3.00000000
2.00000000
1.00000000
0.00000000
1.00000000
2.00000000
1.00000000
0.00000000
1.00000000
2.00000000
3.00000000
4.00000000
3.00000000
2.00000000
1.00000000
0.00000000
1.00000000
2.00000000
3.00000000
4.00000000
3.00000000
2.00000000
1.00000000
0.00000000
1.00000000
2.00000000
1.0...

result:

ok 108 numbers

Test #9:

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

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.21954446
3.16227766
15.03329638
6.70820393
6.00000000
19.10497317
12.00000000
1.00000000
5.65685425
4.12310563
1.41421356
5.09901951
12.36931688
19.23538406
6.00000000
9.48683298
6.32455532
4.12310563
18.02775638
4.47213595
13.34166406
2.23606798
13.15294644
7.07106781
7.28010989
3.00000000
11.045...

result:

ok 1681 numbers

Test #10:

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

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.41421356
18.43908891
4.47213595
12.04159458
14.31782106
10.44030651
19.02629759
15.03329638
3.60555128
8.54400375
18.02775638
17.46424920
20.00000000
5.00000000
13.34166406
10.04987562
18.02775638
16.00000000
1.41421356
19.10497317
17.00000000
12.16552506
10.04987562
9.84885780
13.15294644
11.7046...

result:

ok 1681 numbers

Test #11:

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

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.34166797
7.61577311
19.23539988
17.26268044
14.14213562
18.02776437
10.19804688
11.70469991
6.00000000
16.03121954
14.03567684
3.00000000
7.28012529
20.09975124
14.14213959
13.00000000
16.27880485
4.47213595
8.94427191
5.00000000
2.00000000
18.24828759
15.52417470
4.99999039
13.15293061
14.560219...

result:

ok 1681 numbers

Test #12:

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

input:

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

output:

7.07106781

result:

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

Test #13:

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

input:

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

output:

7.07106682

result:

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

Test #14:

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

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.00000000
0.00000000
1.00000000
0.00000000
1.00000000
2.00000000
1.00000000
0.00000000
1.00000000
2.00000000
3.00000000
4.00000000
5.00000000
6.00000000
7.00000000
8.00000000
9.00000000
10.00000000
1.41421356
2.23606798
3.16227766
4.12310563
5.09901951
6.08276253
7.07106781
8.06225775
9.05538514
1....

result:

ok 36 numbers

Test #15:

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

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.31827319
3.14737924
3.04300366
5.60113966
6.29475848
6.55343850
6.08600733
7.48016453

result:

ok 8 numbers

Test #16:

score: 0
Accepted
time: 124ms
memory: 11800kb

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.99886570
14.52542302
21.07310212
31.84318911
115.92489501
49.99139105
60.50662972
69.95813004
134.90230815
90.17256143
100.22015141
110.15485289
119.83813806
169.25925992
139.85771381
149.90386261
159.81303402
169.92400891
209.99705092
189.71365104
199.62297502
209.78857266
219.72774753
229.76351...

result:

ok 99999 numbers

Test #17:

score: 0
Accepted
time: 118ms
memory: 11748kb

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.00000000
15.29584131
21.47208150
30.83930852
35.00655527
50.93145811
60.50661983
70.36379544
80.00703894
90.05617132
100.00063329
110.05050828
119.83812809
129.88519799
134.86807648
149.83387464
159.95046968
169.92399894
174.78545521
189.62941625
199.66046985
209.73856580
219.64591632
229.6395898...

result:

ok 99999 numbers

Test #18:

score: 0
Accepted
time: 128ms
memory: 10412kb

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.00000000
11.79353733
15.00685157
30.31687409
40.11390682
50.14093372
60.17558432
70.36379544
80.12553480
89.85635146
100.00063329
109.95516961
119.76728224
129.81213198
139.93267085
149.71386006
159.75364661
169.73874122
179.90046715
189.81890238
194.75685868
209.84331316
219.61182461
224.7235011...

result:

ok 99999 numbers

Test #19:

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

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.24811448
1548.72811091
1574.07085019
1568.85515661
1558.58257814
1562.01476410
1556.58427178
1558.56463801
1566.85054816
1566.94850782
1544.53941221
1556.45519778
1555.18223227
1562.69996658
1569.16389539
1561.12101686
1545.52168010
1543.06468182
1557.13424685
1564.84673773
1564.24457398
1553...

result:

ok 1781 numbers

Test #20:

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

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.06834345
455444.03730527
455456.30660965
455477.37004875
455453.18351504
455440.18706223
455465.03076494
455465.71064261
455475.71220190
455459.63788507
455454.60356876
455458.90591079
455452.06328764
455464.83513712
455466.56602079
455472.10670742
455449.82285753
455444.30225259
455438.49659...

result:

ok 1781 numbers

Test #21:

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

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.47448608
284359.79373265
284363.97387831
284349.90822609
284348.81350971
284360.55981077
284354.99743162
284364.12474534
284362.68000458
284362.49679082
64050.72021068
284352.72599715
284351.40094960
284351.03783208
284357.90779170
284361.14362040
284357.18470095
284366.54186089
284364.949240...

result:

ok 1781 numbers

Test #22:

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

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.62139464
393120.74490368
393130.18935159
393123.05859969
393128.13429690
393119.03337907
393131.71643136
393123.27562186
393117.28858539
393128.21922607
393128.29763733
393121.16589612
393113.82988658
393115.18905691
393125.09845926
393130.38305493
393119.66116435
393125.91892153
254167.51558...

result:

ok 1781 numbers

Test #23:

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

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.93541504
234686.78076298
234696.22405210
234689.23462419
234681.50983354
234688.32522228
234690.98553042
234685.31470147
234697.88306297
234685.98333338
234683.34292096
234692.97809747
234686.07639461
234686.24027940
396836.11492530
313138.09786058
234682.10129800
234696.29277395
234692.35691...

result:

ok 1781 numbers

Test #24:

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

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.44641864
427613.18543998
427604.19693780
427623.36897197
427607.13360154
427612.81641323
427615.35449848
427597.85368265
427608.72995587
427602.78677934
427604.03770326
427604.61211882
427612.18063345
427618.99499669
427621.96392006
427601.41037060
427606.96271249
427626.12533372
427611.92394...

result:

ok 1781 numbers

Test #25:

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

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.91651689
4368.07587067
4363.00200988
4351.15785637
4369.07182157
4360.81011560
4359.49612862
4364.15210823
4372.29116492
4363.80849164
4356.86540608
4360.21154821
4362.49634419
4358.76483164
4357.22915524
4358.93191046
4358.00252090
546468.25083996
4358.10292169
4360.01941740
4352.02646750
4361...

result:

ok 1781 numbers

Test #26:

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

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.60332544
730974.08228289
730965.48510232
730979.79298755
730970.73839133
731000.14045905
730970.30922725
730996.55786905
730961.61555121
730976.59082961
730959.80011717
730979.52849791
730970.64454855
730971.74432133
730991.90143698
730983.23041893
832464.81883935
730992.44968942
730985.47498...

result:

ok 1781 numbers

Test #27:

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

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.20626779
1169879.34847452
372097.80616288
372088.17689015
372081.49799025
372081.01466975
372057.62184673
372089.50173864
372069.49100418
372077.25418042
372071.92620064
372082.75091222
372088.44402755
372062.60323999
372062.17232248
372088.06569016
372082.01326206
372086.23059860
372078.9249...

result:

ok 1781 numbers

Test #28:

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

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.07376774
10.85847446
7.64939995
8.50496141
9.38455903
7.83287542
1.44265210
15.73422639
16.86631151
12.60790007
21.79197009
6.47758784
6.17592785
13.78820372
8.17517516
14.16388424
18.25790017
6.94837700
9.51754494
4.64944953
12.84994919
9.20473605
22.85332238
7.17793701
7.93544876
9.80133297
0.4...

result:

ok 1781 numbers

Test #29:

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

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.00000000
10.19803903
12.42802656
1330347.14979610
8.23580155
10.50979753
11.66673469
8.60232527
15.56737440
3.60555128
19.20937271
20.44636456
7.21110255
12.74139497
12.38477631
11.96933312
8.93194569
3.46410162
8.54400375
398065.76145779
14.14629807
12.04159458
11.96687347
22.13073773
22.8035085...

result:

ok 1781 numbers

Test #30:

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

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.40402053
20.38893259
10.21955664
20.92534570
5.04413112
12.24807921
2.87548450
2.68850551
16.34866142
12.64724874
11.53339403
1.36333233
23.96443357
2.72424054
9.61474174
6.29381249
6.83516567
7.69062799
5.92933645
7.35812290
5.54941457
3.07170204
19.26941858
2.24930980
1.36011370
14.42871176
0.28...

result:

ok 1781 numbers

Test #31:

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

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.93989125
7.63615484
9.39324017
10.38278618
14.47032347
7.06354247
8.73037670
24.09276695
201368.83607598
5.39690589
9.10644503
17.82881558
24.47023713
17.73800174
11.39968453
13.56808329
18.69486908
19.40796007
17.46101058
11.63631148
18.95652422
8.98967361
10.54727186
21.34019084
9.68001151
17.2...

result:

ok 1781 numbers

Test #32:

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

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.71450244
25.43608921
16.87629565
26.16413213
11.36667833
31.20004726
26.95662280
25.93429054
22.98766678
28.22278808
10.74902603
5.69908752
26.93079639
21.33652365
24.21201408
25.57493205
27.68954760
1162982.79050175
17.39208616
11.68002578
7.97548004
15.18544875
7.46952906
35.44161152
13.5933209...

result:

ok 1781 numbers

Test #33:

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

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.12090029
12.27722767
25.75671338
6.99411152
23.98251597
7.03921647
11.85113629
20.90902381
16.75154439
14.31298192
15.17241821
24.93579736
17.09370493
18.67713019
14.73435228
11.49629540
2.53071013
5.17520850
14.12610466
14.08787296
26.08686086
19.54118000
14.98026133
11.74941162
19.13465097
19.1...

result:

ok 1781 numbers

Test #34:

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

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.93265087
7.21110255
5.00000000
12.18229432
18.00000000
0.27740242
12.93304077
1024855.13624226
12.41912356
3.25576412
5.66388503
9.09781783
16.05615147
16.12698340
4.53887256
12.77877989
11.46115754
10.69963570
4.12310563
18.57426704
11.90798052
0.72629873
1.48542063
16.49242250
11.54934639
15.66...

result:

ok 1781 numbers

Test #35:

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

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.56875398
25.12981264
22.08819799
19.74962707
15.39533234
17.10471349
17.16955228
13.35059610
22.12051687
22.16603146
26.00609505
12.79694771
17.01445854
18.16678127
24.45176430
23.17669690
24.99396762
0.99205470
24.79599353
17.80896222
16.78718678
752464.59421517
17.13439888
15.38655863
18.129613...

result:

ok 1781 numbers

Test #36:

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

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.23606798
8.79600300
15.69729177
19.47576133
9.05538514
11.39467105
5.09901951
19.00000000
8.61941834
9.19252551
16.67202080
714191.23933720
13.98942591
2.65241404
9.84885780
16.26752801
9.52938042
2.70820393
5.76247002
15.36458917
9.09995006
2.15231681
446893.44889470
20.57703121
16.06101732
5.889...

result:

ok 1781 numbers

Test #37:

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

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.97777229
2.75012077
0.84677771
1.46407105
0.58578644

result:

ok 5 numbers

Test #38:

score: 0
Accepted
time: 26ms
memory: 5448kb

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.46248817
15.75079676
53.67824224
82.36844407
13.98380097
37.94962441
19.41738274
26436.95480431
16.27654605
17.45511546
41.13974262
10.88638513
2.54127702
43.12407919
91.93683274
29490.05864560
25443.53864369
26521.91753581
25.70349593
22.20988222
21.22932966
36.80474279
11423.11015666
68.65261287...

result:

ok 100 numbers

Test #39:

score: 0
Accepted
time: 90ms
memory: 8552kb

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.97226336
1395.00626269
65837.71604013
3799.08578264
3433.75828384
194.09069223
7369.21072563
265305.15313839
8568.33430216
4911.65076925
54497.52432893
3603.75368050
3575.12081885
159352.01784933
3626.60867667
100481.17887101
74738.61238273
2868.23912531
3345.94719578
3533.45805107
86886.70645...

result:

ok 100000 numbers

Test #40:

score: 0
Accepted
time: 110ms
memory: 7528kb

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.63617254
5614.80460006
18063.49135982
48666.35013700
29146.20215379
1712.93252010
166623.04746191
37945.22612434
14861.68974927
52982.28356152
2858.97812041
13281.34954043
2313.81728523
9696.14644292
24522.00643096
915.75526489
11130.98876134
94958.55636576
12364.17080247
17705.05433204
17545.5...

result:

ok 100000 numbers

Test #41:

score: -100
Wrong Answer
time: 129ms
memory: 10392kb

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.00000000
7.00000000
7.00000000
7.00000000
9.00000000
9.00000000
9.00000000
9.00000000
1.00762098
2.00000000
11.40176214
11.40175425
8.00630550
9.00001000
9.00000000
20.12461180
0.11077028
2.00000000
19.31321724
19.31320792
16.01261100
18.00002000
18.00000000
32.44996148
0.50402669
2.00000000
27.89...

result:

wrong answer 8233rd numbers differ - expected: '0.0019575', found: '0.0019537', error = '0.0000038'