QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#338350#5570. Epidemic Escapeucup-team1198#WA 3800ms32264kbC++208.0kb2024-02-25 20:51:322024-02-25 20:51:33

Judging History

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

  • [2024-02-25 20:51:33]
  • 评测
  • 测评结果:WA
  • 用时:3800ms
  • 内存:32264kb
  • [2024-02-25 20:51:32]
  • 提交

answer

#pragma GCC optimize("fast-math")
#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define int int64_t
using ld = __float128;

ld abs(ld x) {
    if (x > 0) return x;
    return -x;
}

struct IVector {
    int x;
    int y;

    IVector(int x = 0, int y = 0): x(x), y(y) {}
    IVector(const IVector& a, const IVector& b): x(b.x - a.x), y(b.y - a.y) {}
};

IVector operator-(const IVector& a) {
    return {-a.x, -a.y};
}

int operator%(const IVector& a, const IVector& b) {
    return a.x * b.y - a.y * b.x;
}

bool hp(const IVector& v) {
    if (v.y == 0) return v.x > 0;
    return v.y > 0;
}

bool operator<(const IVector& a, const IVector& b) {
    if (hp(a) != hp(b)) return hp(a);
    return a % b > 0;
}

bool operator==(const IVector& a, const IVector& b) {
    return a.x == b.x && a.y == b.y;
}

istream& operator>>(istream& in, IVector& v) {
    in >> v.x >> v.y;
    return in;
}

const int MAXN = 1e5 + 100;
bool is_bad[MAXN];

struct Vector {
    ld x;
    ld y;

    Vector(ld x = 0, ld y = 0): x(x), y(y) {}
    Vector(const Vector& a, const Vector& b): x(b.x - a.x), y(b.y - a.y) {}
    Vector(const IVector& a): x(a.x), y(a.y) {}
    Vector(const IVector& a, bool inv) {
        ld ln = a.x * a.x + a.y * a.y;
        x = a.x; y = a.y;
        x /= ln;
        y /= ln;
    }

    ld sqlen() const { return x * x + y * y; }
};

Vector operator-(const Vector& a, const Vector& b) {
    return Vector(b, a);
}

Vector operator+(const Vector& a, const Vector& b) {
    return {a.x + b.x, a.y + b.y};
}

ld operator%(const Vector& a, const Vector& b) {
    return a.x * b.y - a.y * b.x;
}

ld operator*(const Vector& a, const Vector& b) {
    return a.x * b.x + a.y * b.y;
}

const ld EPS = 1e-26;

const int MAXK = 5;

vector<Vector> convex(vector<Vector>& p) {
    if (p.empty()) return p;
    int n = p.size();
    Vector minp = p[0];
    for (int i = 1; i < n; ++i) {
        if (p[i].x < minp.x) {
            minp = p[i];
        } else if (p[i].x == minp.x && p[i].y < minp.y) {
            minp = p[i];
        }
    }
    sort(p.begin(), p.end(), [&](const Vector& u, const Vector& v) {
        if (abs((u - minp) % (v - minp)) < EPS) {
            return (u - minp).sqlen() < (v - minp).sqlen();
        }
        return (u - minp) % (v - minp) < 0;
    });

    p.push_back(p[0]);
    /**for (auto elem : p) {
        cout << (double)elem.x << " " << (double)elem.y << " : ";
    }
    cout << endl;*/
    vector<Vector> st;
    int sz = 0;
    vector<Vector> p1;
    for (auto v : p) {
        while (sz >= 2 && (st[sz - 1] - st[sz - 2]) % (v - st[sz - 1]) >= -EPS) {
            p1.push_back(st.back());
            st.pop_back();
            --sz;
        }
        st.push_back(v);
        ++sz;
    }
    st.pop_back();
    p = p1;
    return st;
}

vector<Vector> get_bst(const Vector& dir, const vector<Vector>& p, int cnt) {
    if (p.empty()) return p;
    int n = p.size();
    int k = 0;
    while ((1 << k) < n) ++k;
    int i = 0;
    while (k >= 0) {
        int i1 = (i + (1 << k)) % n;
        int i2 = (i - (1 << k) + 2 * n) % n;
        if (dir * p[i1] > dir * p[i]) i = i1;
        if (dir * p[i2] > dir * p[i]) i = i2;
        --k;
    }
    vector<Vector> ans = {p[i]};
    int sz = min(cnt - 1, n - 1);
    int t1 = (i + 1) % n;
    int t2 = (i - 1 + n) % n;
    for (int _ = 0; _ < sz; ++_) {
        if (dir * p[t1] > dir * p[t2]) {
            ans.push_back(p[t1]);
            t1 = (t1 + 1) % n;
        } else {
            ans.push_back(p[t2]);
            t2 = (t2 - 1 + n) % n;
        }
    }
    return ans;
}

mt19937 rnd;
const int MAX = 100000000;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cout << fixed << setprecision(10);
    
    int n;
    cin >> n;
    vector<IVector> p(n);
    int cnt0 = 0;
    for (int i = 0; i < n; ++i) {
        cin >> p[i];
        /**p[i].x = rnd() % (2 * MAX) - MAX;
        p[i].y = rnd() % (2 * MAX) - MAX;*/
    }
    vector<IVector> p1;
    for (int i = 0; i < n; ++i) {
        if (p[i] == IVector()) {
            ++cnt0;
        } else {
            p1.push_back(p[i]);
        }
    }
    p = p1;
    n = p.size();

    int q;
    cin >> q;
    vector<pair<IVector, int>> qu(q);
    for (int i = 0; i < q; ++i) {
        cin >> qu[i].first >> qu[i].second;
        /**qu[i].first.x = rnd() % (2 * MAX) - MAX;
        qu[i].first.y = rnd() % (2 * MAX) - MAX;
        qu[i].second = 5;*/
        qu[i].second -= cnt0;
    }

    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        if (hp(p[i])) ++cnt;
    }
    vector<pair<IVector, int>> ev;
    for (int i = 0; i < n; ++i) {
        ev.push_back({p[i], -1});
        ev.push_back({-p[i], q});
    }
    for (int i = 0; i < q; ++i) {
        if (qu[i].first == IVector()) {
            is_bad[i] = true;
            continue;
        }
        ev.push_back({{qu[i].first.y, -qu[i].first.x}, i});
    }
    sort(ev.begin(), ev.end());
    for (auto elem : ev) {
        if (elem.second == -1) {
            --cnt;
        } else if (elem.second == q) {
            ++cnt;
        } else {
            if (cnt < qu[elem.second].second) {
                is_bad[elem.second] = true;
            }
        }
    }

    vector<Vector> pv;
    for (int i = 0; i < n; ++i) {
        pv.push_back(Vector(p[i], true));
        /// cerr << i << ": " << (double)pv[i].x << " " << (double)pv[i].y << endl;
    }
    vector<vector<Vector>> hulls;
    for (int i = 0; i < MAXK; ++i) {
        hulls.push_back(convex(pv));
        /**for (Vector v : hulls.back()) {
            cout << (double)v.x << " " << (double)v.y << "; ";
        }
        cout << endl;*/
    }
    for (int i = 0; i < q; ++i) {
        if (is_bad[i]) {
            cout << "-1\n";
            continue;
        }
        if (qu[i].second <= 0) {
            cout << "0\n";
            continue;
        }
        int k = qu[i].second;
        Vector dir = qu[i].first;
        vector<Vector> bst;
        for (int i = 0; i < k; ++i) {
            auto res = get_bst(dir, hulls[i], k - i);
            /**vector<Vector> bst1;
            int f1 = 0, f2 = 0;
            for (int i = 0; i <= k && i < (int)bst.size() + res.size(); ++i) {
                if (f2 >= res.size()) {
                    bst1.push_back(bst[f1++]);
                } else if (f1 >= bst.size()) {
                    bst1.push_back(res[f2++]);
                } else if (bst[f1] * dir > res[f2] * dir) {
                    bst1.push_back(bst[f1++]);
                } else {
                    bst1.push_back(res[f2++]);
                }
            }
            bst = move(bst1);*/
            for (auto elem : res) {
                bst.push_back(elem);
                for (int i = (int)bst.size() - 1; i > 0; --i) {
                    if (dir * bst[i] > dir * bst[i - 1]) {
                        swap(bst[i], bst[i - 1]);
                    } else {
                        break;
                    }
                }
                if ((int)bst.size() > k) bst.pop_back();
            }
        }
        long double ans = dir * bst[k - 1];
        /// cout << (double)bst[k - 1].x << " " << (double)bst[k - 1].y << endl;
        ans /= sqrtl(dir.x * dir.x + dir.y * dir.y);
        ans = 0.5 / ans;
        cout << ans << "\n";
        if (ans < -1) {
            cout << n << "\n";
            for (int i = 0; i < n; ++i) {
                cout << p[i].x << " " << p[i].y << "\n";
            }
            cout << qu[i].first.x << " " << qu[i].first.y << " " << qu[i].second << endl;
            return 0;
        }
    }



    return 0;
}

详细

Test #1:

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

input:

5
5 -3
5 4
-6 2
-5 0
4 1
2
-3 -10 1
6 -9 1

output:

8.7002554241
3.2260195623

result:

ok 2 numbers

Test #2:

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

input:

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

output:

3.1677629681
26.1629509039
5.4614883202
6.3639610307
-1
5.2894082216
3.7267799625
4.6097722286
2.9294423792
4.7617289402

result:

ok 10 numbers

Test #3:

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

input:

5
-4 -7
5 0
2 4
-7 -7
4 4
20
0 -5 2
-4 -7 2
-7 7 3
4 -4 3
-7 4 3
4 -4 1
2 4 1
6 -7 2
4 -4 2
4 4 3
5 4 1
-1 9 2
8 9 3
4 -4 2
6 3 3
-10 -3 2
-7 7 1
9 -4 1
-4 -7 3
-2 0 2

output:

7.0000000000
5.1305276580
-1
-1
-1
3.5355339059
2.2360679775
11.9854077945
15.3206469257
3.5355339059
2.4627400913
4.5276925691
3.7629983059
15.3206469257
2.9814239700
5.6217035048
7.0710678119
2.7357938338
-1
8.1250000000

result:

ok 20 numbers

Test #4:

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

input:

100
63 -48
20 -62
-81 -31
-17 -93
2 -74
72 25
-71 37
-71 17
56 67
-47 65
-89 14
62 30
-71 -33
14 -53
-57 -52
30 80
-14 -69
-45 -19
-54 -71
58 -20
-57 12
5 -56
-76 -2
26 61
24 60
10 -97
-63 38
17 81
-43 -38
44 35
-86 37
62 72
77 11
41 29
14 81
77 55
-54 -33
-43 -51
76 14
55 47
43 24
69 -13
16 75
11 9...

output:

26.7586788688
29.5714059979
24.6221445045
27.7717456547
26.6783667129
24.4237024605
28.8933481964
29.7761695578
31.9403629705
27.2149016024
31.7280950457
27.0711605517
25.2991100306
26.8710651521
28.9958394534
28.3563142462
29.9872588920
25.6496237196
25.1496681332
28.3011569706
28.6117519545
26.690...

result:

ok 100 numbers

Test #5:

score: 0
Accepted
time: 135ms
memory: 5680kb

input:

10000
-3 3
-6 2
-4 1
-2 -5
5 -6
-7 -2
0 7
1 -4
8 0
-4 4
-6 -2
5 0
2 9
-4 -8
0 -8
7 4
-7 2
3 3
4 1
-1 7
-4 -2
6 0
3 -5
-7 2
0 -9
7 0
7 3
-6 0
1 7
6 2
2 -9
1 8
3 -3
2 -9
4 2
4 -5
6 0
-3 6
7 3
0 8
0 -4
7 0
-5 8
5 -5
-5 -1
0 9
-4 -3
-9 -1
7 -2
-7 -2
4 0
-6 6
-3 4
6 7
2 5
-8 -5
0 5
4 0
0 -4
0 -6
-5 3
-5 ...

output:

2.1549170046
2.1672659357
2.0676430855
2.1118419787
2.1118419787
2.1118419787
2.1249872786
2.1213203436
2.0275875101
2.0928822829
2.1415372144
2.0615528128
2.1549170046
2.0000000000
2.1213203436
2.1672659357
2.0676430855
2.0203050891
2.0676430855
2.1415372144
2.1213203436
2.0000000000
2.1213203436
2...

result:

ok 10000 numbers

Test #6:

score: 0
Accepted
time: 161ms
memory: 5680kb

input:

10000
-90174 318421
-37261 138897
-260388 -302590
-906833 35071
317743 -283220
390311 -85301
880987 325969
-315218 -116767
103089 -8223
-134988 -973121
-444593 229407
-552060 549321
265624 -337609
-264546 322379
28687 110143
467764 303005
-335748 32188
213125 274156
240105 751
-81255 -129323
148563 ...

output:

218.3023759373
481.6627119891
792.1850756018
579.9542618493
807.7094462678
242.5921754846
882.2675147667
530.7807802597
664.1821759610
796.3607397675
662.7071678987
639.0726192787
125.8211827153
745.7291752667
732.4967218100
676.5327801482
808.9964118683
427.9627407901
1298.3736892031
616.3789303001...

result:

ok 10000 numbers

Test #7:

score: 0
Accepted
time: 1647ms
memory: 29076kb

input:

100000
-14593321 17388753
13488647 1223793
33907737 -8731155
-14502324 73522129
-13933178 -13752140
9462275 13349398
14636622 31405249
5160247 -69775840
-49415260 -40092130
-9926862 -25806124
14982829 -8025116
-5492901 4568113
48872077 86636033
19374632 32538501
-16657133 -11624530
-15398598 -966935...

output:

1331.4977763324
1193.9602287451
1171.2427261871
1856.2890362990
2681.8829458540
1170.8707408363
1128.3614715722
1855.8783379892
3518.3241479702
1541.7860082154
1515.0151223165
1124.4065660466
2146.7167113138
1179.4306789471
1164.1588782715
1251.5110829082
2737.3506509053
1117.3515869945
2213.1263918...

result:

ok 100000 numbers

Test #8:

score: 0
Accepted
time: 1739ms
memory: 28804kb

input:

100000
-60674143 79489917
99210432 12541486
-99948887 -3196593
57015830 -82153478
10407645 99456921
-90320128 42921703
93983821 34161956
96773928 -25195355
69603194 71801068
27259746 -96212811
96031961 27890165
76618755 -64261689
-99095784 13417302
-95521354 -29591717
-34815155 -93743823
-93393132 -...

output:

50000002.1072942819
49999997.6607843053
49999998.2836471890
49999996.0395986806
50000004.6735046402
50000000.4417728307
49999996.2729277107
50000000.7763232978
49999996.6611837155
50000000.5426376573
49999997.2567733076
49999999.7021081795
49999996.1309134627
49999996.1276430841
49999997.8455304944
...

result:

ok 100000 numbers

Test #9:

score: 0
Accepted
time: 1732ms
memory: 30060kb

input:

100000
28442101 95869943
64560849 76366848
-85662377 51594149
95580169 -29401185
-40181553 -91572058
67627360 -73665047
82527643 56472888
29700208 95487675
87983116 -47528622
62992785 77665358
-2222699 99975284
-64132427 76726992
-76047272 64936977
87016456 49276108
95274227 30377974
-62944509 -7770...

output:

50000004.9411571359
49999996.5871423045
49999997.0994975140
49999998.4855410000
50000003.6390350672
50000002.2691187814
49999996.7847972605
49999996.4713342653
50000000.4138043576
49999997.2998203792
50000001.0508446163
49999994.9030463941
50000003.7846678008
49999998.0524404329
49999995.3312548597
...

result:

ok 100000 numbers

Test #10:

score: 0
Accepted
time: 1819ms
memory: 29448kb

input:

100000
66926611 74302272
-39804607 -91736532
-31850108 94792239
-94396583 -33004302
-57766222 81627580
-80246004 59670576
74979879 -66166588
37426246 -92732280
-40775354 -91309200
99674197 8065507
94244794 -33435279
-24613128 -96923641
28694420 -95794726
97637671 -21607478
-49066338 -87134919
612455...

output:

49999998.4770237698
49999995.4357772327
50000002.5056946629
49999999.2722293835
50000002.3385189594
49999996.0671414029
49999999.1335463143
49999994.5402301618
49999994.6179780847
49999995.7053462137
49999997.6019228992
49999995.1414506520
50000003.5665951512
49999994.9688381011
50000003.6064968757
...

result:

ok 100000 numbers

Test #11:

score: 0
Accepted
time: 1720ms
memory: 30028kb

input:

100000
31516589 94903656
70239724 71178504
-57719682 81660501
73612201 67684871
82391354 -56671542
72801723 -68555878
26893692 -96315770
-83483265 55050367
87478845 -48450493
-85026739 52635096
-26511823 96421583
95776532 -28755096
88242174 -47045913
77725402 -62918677
-14344932 98965762
-25054341 -...

output:

49999997.1980685267
49999995.1742068688
49999997.4496326283
50000001.0811396683
49999998.6177088303
49999996.6107622593
50000002.0041374602
50000001.5949047226
49999999.0388268164
49999995.6628384098
49999996.8188693349
49999997.0231123448
50000008.0747477268
49999998.3238768146
49999997.0409773109
...

result:

ok 100000 numbers

Test #12:

score: 0
Accepted
time: 1741ms
memory: 29776kb

input:

100000
-77953946 -62635297
-97003745 24295529
-95559516 -29468254
-37774475 -92590972
-78235761 62282941
24449261 96965108
-32126090 -94699061
-90361637 -42834246
-15234257 -98832767
-67393723 -73878858
-77089954 63695658
-87433336 -48532575
45142341 -89230981
80543145 -59268883
99006350 -14062036
-...

output:

49999998.5750103303
50000003.7170186879
49999996.5283633763
50000006.8174292819
49999996.5753166218
49999994.9757974577
50000000.3901771114
49999998.2941943145
50000003.5703424938
49999998.3413638914
49999996.3185632805
50000002.0038767871
49999996.4221767782
49999996.5544415438
49999996.8805126344
...

result:

ok 100000 numbers

Test #13:

score: 0
Accepted
time: 2231ms
memory: 28924kb

input:

100000
-14994761 -98790003
-52791662 84821895
87513045 48313812
19785427 97922747
98912337 -14130131
-4520530 -99837938
93690283 34834919
99547007 8570663
86380533 -50241768
-46722739 88350371
69496929 -71791216
-85910197 -51161960
5199588 99844597
11410781 -99298438
-99814172 5122831
99748209 57815...

output:

49950309.3056237988
49950587.9321183814
49950271.2551974819
49950284.2250954475
49950441.6709376118
49950141.2846822302
49950288.3766497255
49950469.2183907807
49950744.1464028661
49950688.2312025683
49950339.5676553654
49950216.2988869351
49950092.5740196349
49950416.5313250064
49950177.6632704128
...

result:

ok 100000 numbers

Test #14:

score: 0
Accepted
time: 2654ms
memory: 29568kb

input:

100000
87107311 49115334
-98093001 -19436093
86159431 -50759733
-90576186 -42378693
99725385 7405849
-93030414 -36678893
7164898 99742981
88908273 -45774642
-87848897 47776244
98650729 -16371688
-13992770 99016167
-36675953 93031566
-28482368 95857989
-38312130 -92369793
86372731 50395931
-50997291 ...

output:

50000000.7186129023
50000003.4578220000
50000002.5753960186
50000005.7825245185
50000004.8504965691
49999997.1794144417
49999999.0929900942
50000007.7559094000
49999999.8994686271
49999998.5924756615
49999999.5618602670
49999996.6120058976
50000000.3916456642
50000000.1392825022
50000003.5947728352
...

result:

ok 100000 numbers

Test #15:

score: 0
Accepted
time: 2600ms
memory: 31552kb

input:

100000
87353211 -48676647
78574311 -61855286
1089525 99994063
-99999914 -125343
-79940915 -60078697
97608574 -21738565
-99570798 9254977
-57082835 -82106930
77989099 62591525
-36640991 -93045345
-82795 -99999957
99857762 5331654
91364668 40650900
-89488349 -44629962
24733984 96892872
87543386 483337...

output:

50000004.4163447830
50000010.3507144310
49999998.8286816270
50000001.8170302164
49999997.7336274903
50000005.7352134182
50000000.1785098867
50000002.9259517058
50000007.6415535801
49999999.7526413318
50000008.9412595017
50000002.7691493718
50000006.5465015175
50000001.1436343580
49999997.1777759802
...

result:

ok 100000 numbers

Test #16:

score: 0
Accepted
time: 2517ms
memory: 30744kb

input:

100000
-95807142 28504127
58593535 -80943524
-99766431 5986168
93220087 -35989826
3645498 -99841657
69856363 -71476864
6430623 99747801
99074166 -13444307
25226151 96750874
-99820804 -4584947
80958147 58644185
99854141 3972407
93127038 36267563
83656508 -54710699
73943321 -67286687
22540877 -9736065...

output:

49951675.8764737743
49951660.7759727305
49951740.4114056055
49951465.4638304028
49950200.2577471236
49950954.5130789854
49951162.3204078494
49950823.9987229996
49951011.4364624367
49951169.7614416876
49950251.9870868726
49950960.8967498478
49951548.7213694641
49950976.9117757239
49950703.5493174638
...

result:

ok 100000 numbers

Test #17:

score: 0
Accepted
time: 3027ms
memory: 30380kb

input:

100000
-18866705 98167110
96374803 -26445175
-90527905 42406852
93525949 35171769
-99675297 7020406
-99946706 -2220134
31631621 -94776631
-46384811 88576816
-2476324 99950315
69306249 -72003171
-30910251 -95067123
85457008 51882654
82372940 -56613508
6032490 99757677
99488049 -9473775
97295326 22667...

output:

49950435.4342463168
49950523.6429177893
49951727.0368673848
49950791.7197091727
49952062.1846697600
49951220.3037158485
49950723.9434544286
49951030.2751690404
49951362.7755594238
49951028.0508876230
49951744.1141123088
49951224.7437644795
49952317.4008079955
49951224.1601771633
49951151.4789893492
...

result:

ok 100000 numbers

Test #18:

score: 0
Accepted
time: 2528ms
memory: 28676kb

input:

100000
-94544376 30244008
-5524553 -99134196
64736465 74935295
-10781223 -98537615
-27540414 96110283
94534101 -30554453
-49000527 -87040163
-70553197 70503800
90093758 -41264733
51497088 84792240
-50688507 -85177162
95747827 28411115
-85773541 -50275968
-34190721 93830767
-42611828 90282250
-315970...

output:

49503286.6071341862
49503940.1660004199
49500902.0574530688
49502328.8001762668
49504050.8899425749
49503864.7113224403
49502762.9502231849
49505338.4543824051
49503140.1828940405
49508220.5136476464
49506314.7348970712
49508005.3967640638
49501854.4901581556
49506908.0257155500
49503251.9579029106
...

result:

ok 100000 numbers

Test #19:

score: 0
Accepted
time: 2741ms
memory: 30008kb

input:

100000
-72724429 68353169
-23398454 96972722
98697156 15295066
-50053634 86257978
95660227 -25689933
-98427638 12257835
-95720479 25986032
99360720 -9958797
-34453585 -93167496
97657115 21470158
-61854668 77939046
-78666489 60608092
99656422 -4271277
37176490 92108858
92266107 -36908241
84966021 -52...

output:

49505232.2522462104
49505902.9530284100
49506391.3517989339
49501384.8619998096
49501974.5375367875
49503956.2921274886
49506260.8484404916
49507848.9578431358
49507844.1977249836
49507646.9159879079
49505334.2111403260
49504283.4305713325
49503897.6784182638
49506239.9631956961
49506420.6701118899
...

result:

ok 100000 numbers

Test #20:

score: 0
Accepted
time: 2890ms
memory: 31524kb

input:

100000
-98189095 15784434
89982407 42479712
-98538151 10378719
48446566 -87123427
90936804 -40512021
67828507 72315413
-19102654 97627943
-40632682 -90422395
-71928032 68028353
59463681 -80194272
-61979681 77927882
-89859188 -41650204
-40753972 -90873220
-31802337 -94326140
29901118 94629634
8981744...

output:

49501432.7022043765
49504111.9000156403
49506914.0037283619
49504020.3841625653
49500748.1808290217
49509533.2816175665
49504423.6514928474
49503519.1264973206
49507687.1662349230
49501887.8451572912
49501129.4738505480
49506066.7849481715
49503294.6517206474
49500496.9255725455
49503260.6522218648
...

result:

ok 100000 numbers

Test #21:

score: 0
Accepted
time: 2655ms
memory: 32264kb

input:

100000
74210313 -66772568
-82118759 55744795
-40558611 -90552265
-80801514 58093666
-87555090 46582002
-96330979 24086781
39402894 91628283
56594773 -82141487
39313600 91784698
89239441 43417687
-95774367 28264902
32961837 93669012
-85873036 -51077556
-27532569 -96083438
82705246 -55505999
-22508180...

output:

49506572.9114001307
49507188.3698279338
49504015.5868492220
49502226.2551336864
49511712.3791654684
49508088.3725657533
49508038.4721606655
49511153.9459437267
49503445.7644251330
49505408.2422356359
49501120.2191417217
49504635.7946901289
49501929.8603164177
49500674.3593257255
49508683.1372701624
...

result:

ok 100000 numbers

Test #22:

score: 0
Accepted
time: 2592ms
memory: 29052kb

input:

100000
-71207198 55424979
-79825607 -56036270
-83654833 37345395
-91097555 -17973035
-79663519 53088655
40943861 -91076400
84688501 31061641
-96431516 -1566452
-89205053 17120308
66023621 -67658770
-85253305 44553904
-95493219 -8941382
-79301859 45970085
-27319544 -90541866
-90379686 -10409784
-8376...

output:

45036750.1372239081
45027842.8818135627
45013570.7649708689
45012430.8467586790
45008268.5080020579
45035953.6251026984
45011940.3266864407
45033497.6378687234
45035993.0317809311
45018438.5524730843
45010458.6109155562
45008354.7259051865
45032420.0671344288
45019612.3304007581
45010086.5286969899
...

result:

ok 100000 numbers

Test #23:

score: 0
Accepted
time: 2541ms
memory: 30600kb

input:

100000
38905528 81237636
-87968422 -27436984
9608199 91019553
78087433 -61515160
-93465529 27267558
13655649 -92011700
-4844144 -90101777
-76856347 -55299593
7037669 95820739
73512631 -55423174
66171160 -69809341
-38015506 -91878674
92573512 18160315
-89558982 43574979
41250811 89067345
90892069 312...

output:

45035187.3884272974
45009163.6065221989
45033436.3931769841
45019451.0239726607
45022200.7504397128
45014848.4584343798
45024066.2168218609
45004916.9090575680
45009051.6157130487
45011633.8119250022
45006265.9086879572
45025389.7773992522
45018143.2059153051
45004427.2401311876
45017652.0731754354
...

result:

ok 100000 numbers

Test #24:

score: 0
Accepted
time: 2530ms
memory: 30412kb

input:

100000
73858871 59646768
74771059 50581404
69886208 66567485
-98824001 3209940
71195346 65729342
-31147238 89170502
-93247841 -18314860
25371727 94636356
96922565 192144
11319923 -96984253
-90534277 -37798172
92579912 22026541
-85805605 34201581
-34434706 84998535
28174675 -86301411
18885420 9491316...

output:

45004913.3664170944
45049419.1160457681
45013923.5129688185
45018139.6488505513
45036905.8127368647
45014915.9261846652
45021998.4164936971
45005546.4190510395
45013393.3187403220
45031474.2617547221
45023802.2902519771
45024466.4821735796
45028156.9922565102
45028587.9272050929
45021843.4432482475
...

result:

ok 100000 numbers

Test #25:

score: 0
Accepted
time: 2233ms
memory: 29376kb

input:

100000
6192364 97854354
-26396072 -87670473
-15829494 95984810
29977494 -87073709
85322761 44933323
-10724758 96451337
25075242 -88807937
88653656 -28596396
-7234959 97007100
-98015205 5615321
-46753278 -86423176
-84626507 -46187913
58215823 -70504834
88062585 26935126
79507695 56070039
-81885399 -4...

output:

45007894.8356611436
45013616.1135625201
45048543.6061462096
45027729.0330647820
45013317.4985193662
45020005.9202678623
45013214.4532615194
45017977.1928253231
45015065.2213866702
45019880.1661492955
45029719.3585011695
45018055.1420109609
45027958.6147321080
45032293.0370835621
45023771.4683760886
...

result:

ok 100000 numbers

Test #26:

score: 0
Accepted
time: 2563ms
memory: 30352kb

input:

100000
-56925997 -77019489
93686323 23015852
-96967479 14925388
-69298767 71247873
-89975226 -39629378
-81202105 -57862266
-30611438 -91102049
69779237 60415278
85454036 38912399
-23494246 -94997385
11333990 -97239874
26776076 95709458
7400584 -95188065
94132228 33609835
31334391 -91724795
15440367 ...

output:

45031230.0083619330
45031012.6837546242
45051159.9267532924
45057523.9439006005
45021248.9383935129
45034531.5222572914
45010861.9044016793
45036940.6662583623
45011332.8873037123
45014214.3833544224
45031679.2282824025
45012785.3672063191
45001127.1071561677
45030055.9623051226
45008553.3961223973
...

result:

ok 100000 numbers

Test #27:

score: 0
Accepted
time: 3599ms
memory: 29752kb

input:

100000
86473583 -50222687
87983523 47527871
50172327 -86502810
-50052528 -86572186
-81465580 57994464
99757942 6953600
-89115446 45369999
-98572877 16834073
86724085 -49788872
-72244940 -69142374
95384011 -30031466
31730815 -94832244
-96383253 26650854
70233115 71185027
38343247 92356888
-76013019 6...

output:

49999999.7586228521
50000008.2166051716
50000000.6779227292
50000000.2939021082
50000001.3631798390
50000003.8309746773
50000006.2427683944
50000000.8065236151
49999999.1410091690
49999999.9471709273
50000003.5892133464
50000006.9817815303
50000000.3323365254
49999999.1077752938
50000001.2801232773
...

result:

ok 100000 numbers

Test #28:

score: 0
Accepted
time: 3234ms
memory: 30132kb

input:

100000
96098382 27660424
96993975 -24334494
98858570 15065921
-70174372 71242940
59401282 80445550
-34968800 -93686616
-45576276 89010123
-93157321 36355368
-98590008 -16733454
29170468 95650836
81074291 -58540220
92315133 -38443648
88517611 -46525596
99591182 -9033025
17031645 -98538935
-76791060 -...

output:

50000002.8073814431
50000006.7853547087
50000000.4790547740
50000004.3481345908
49999998.9744674788
50000001.3954458934
49999999.8752998912
50000001.5784156011
49999998.1136294755
49999999.9181073581
50000005.6501113988
49999998.1184272590
50000002.6730476043
50000002.3689773089
49999999.5136566772
...

result:

ok 100000 numbers

Test #29:

score: 0
Accepted
time: 3341ms
memory: 30568kb

input:

100000
98649054 -16381761
-99891340 -4660392
85079131 -52550367
98751502 -15752448
38325930 -92364069
16772724 98583333
75122377 66004758
95139156 30798377
-24102560 97051870
89328512 44949025
-83521481 -54992370
-22923261 97337161
-49154851 87085012
67965351 -73353320
-79586737 60547083
44791227 -8...

output:

49999999.1121117739
49999999.9965667215
50000007.3606890037
50000005.2430058987
50000003.3713669858
50000001.6461376810
49999999.2027689088
49999998.5025705049
50000001.1342667707
50000005.6238967574
50000001.9535053402
49999997.6047677986
49999999.4744112493
49999997.5776111370
49999999.7111565205
...

result:

ok 100000 numbers

Test #30:

score: 0
Accepted
time: 3800ms
memory: 28620kb

input:

100000
7197545 -99740639
39789850 91742935
-44563738 -89521349
92588284 -37781069
89874957 43846213
-97082384 23979340
52035210 85395169
87881876 -47715555
-25428031 -96713047
6688701 99776051
31394586 94944081
66622083 -74575443
81096253 -58509804
-98223145 18767345
10583592 -99438356
-97020186 -24...

output:

50000004.5663040247
50000003.5358221928
50000002.4380777535
50000003.4707936333
50000002.5150919834
50000002.5643678377
49999999.0977621874
50000000.9625408246
50000004.4613811056
50000006.1052059154
50000000.5085418178
50000006.7776011415
50000000.1926826985
50000000.0610389951
49999998.5912907205
...

result:

ok 100000 numbers

Test #31:

score: 0
Accepted
time: 3502ms
memory: 30296kb

input:

100000
48053189 87697724
-99230647 -12380496
71228034 -70189504
-99862038 -5250874
-92715593 -37467545
26308785 -96477183
91137520 41157649
86371053 50398812
-99541893 -9560913
-96837592 24949526
-28842311 95750301
-99906431 4324846
32704032 -94501032
-98983846 14219579
-98402231 17804504
42162900 9...

output:

50000008.0333089258
49999999.0218331876
50000004.5182560215
50000002.0531451263
50000003.5144370843
50000006.6211119407
50000006.6567161131
50000008.2145737814
49999999.5053149886
50000003.4625811899
50000003.3178028896
50000005.3879691075
50000005.4960163494
49999998.6158779209
49999999.2355735264
...

result:

ok 100000 numbers

Test #32:

score: -100
Wrong Answer
time: 3510ms
memory: 29812kb

input:

100000
-23951830 97020265
-79900659 60056128
-83964098 54143803
97074821 23809857
61007903 79212713
-45094976 89223718
-89377964 44681664
-98513176 -17056240
-27426886 -96062608
56189487 82666265
18047227 -98345883
-99936265 1286532
18608822 98231586
-56949101 82157764
99503767 -8898358
52721687 -84...

output:

49951674.1879358572
49951419.3102471677
49951190.6025995812
49951412.5821994062
49951643.3201369413
49952981.5404847637
49951531.5661155800
49950744.7078593344
49951759.6741204799
49952147.6803641543
49950940.6456706008
49951560.3948296950
49951096.6605874512
49952163.0136613007
49952791.2038600241
...

result:

wrong answer 1723rd numbers differ - expected: '49951583.0859069', found: '49951979.5746075', error = '0.0000079'