QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#338375#5570. Epidemic Escapeucup-team1198#TL 3980ms32732kbC++208.2kb2024-02-25 21:05:202024-02-25 21:05:22

Judging History

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

  • [2024-02-25 21:05:22]
  • 评测
  • 测评结果:TL
  • 用时:3980ms
  • 内存:32732kb
  • [2024-02-25 21:05:20]
  • 提交

answer

#pragma GCC optimize("fast-math,Ofast,unroll-loops")
#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-32;

const int MAXK = 6;

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;
}

int norm(int x, int n) {
    while (x >= n) x -= n;
    return x;
}

int reduce(int x, int n) {
    while (x < 0) x += n;
    return x;
}

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 = norm((i + (1 << k)), n);
        int i2 = reduce((i - (1 << k)), 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 = norm((i + 1) , n);
    int t2 = reduce((i - 1) , n);
    for (int _ = 0; _ < sz; ++_) {
        if (dir * p[t1] > dir * p[t2]) {
            ans.push_back(p[t1]);
            t1 = norm((t1 + 1), n);
        } else {
            ans.push_back(p[t2]);
            t2 = reduce((t2 - 1) , 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], max(k - i, (int)1));
            /**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: 3812kb

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: 3908kb

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: 3944kb

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: 3968kb

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: 174ms
memory: 5636kb

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: 196ms
memory: 5812kb

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: 2003ms
memory: 30492kb

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: 1549ms
memory: 28092kb

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:

49999995.0818661941
49999995.9004091124
49999995.3149217014
49999995.3054674002
49999994.5577050093
49999996.4862814266
49999994.6940732430
49999995.1368903976
49999995.7255437915
49999995.4937630891
49999997.2567733076
49999994.7944017604
49999994.9287077410
49999995.7829386723
49999994.9440986489
...

result:

ok 100000 numbers

Test #9:

score: 0
Accepted
time: 1615ms
memory: 29464kb

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:

49999994.8309710390
49999995.5183788592
49999994.9251787021
49999995.5234946922
49999994.8275525085
49999994.6394857935
49999994.8678172358
49999996.4713342653
49999995.0233866907
49999995.4033335249
49999994.9916431116
49999994.9030463941
49999995.6710114568
49999995.2659545375
49999995.3312548597
...

result:

ok 100000 numbers

Test #10:

score: 0
Accepted
time: 1530ms
memory: 32732kb

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:

49999995.7715908148
49999995.4357772327
49999996.4043741883
49999994.8179789327
49999997.2285060446
49999995.8582851484
49999995.0825320438
49999994.5402301618
49999994.6179780847
49999995.4909426205
49999995.5851056779
49999994.7581311457
49999997.0426210118
49999994.9688381011
49999995.9953611581
...

result:

ok 100000 numbers

Test #11:

score: 0
Accepted
time: 1534ms
memory: 30468kb

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:

49999995.1416609891
49999995.1742068688
49999995.8579723495
49999997.1304232285
49999995.6565237637
49999995.2441420847
49999995.3516391511
49999994.6824236612
49999995.6391572192
49999995.6166996073
49999995.0758054910
49999997.0231123448
49999994.7090391855
49999996.2098523259
49999995.4048886005
...

result:

ok 100000 numbers

Test #12:

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

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:

49999994.8800609984
49999995.6036443484
49999995.4473164310
49999994.8234286120
49999994.7814365927
49999994.9757974577
49999994.9918332584
49999996.4288837310
49999995.4920812346
49999996.1784076709
49999995.1575361160
49999994.5227592685
49999995.0962231795
49999994.7197688141
49999995.0631763546
...

result:

ok 100000 numbers

Test #13:

score: 0
Accepted
time: 2733ms
memory: 31084kb

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: 2292ms
memory: 31912kb

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:

49999995.7797225483
49999994.6245876048
49999998.3509637771
49999995.5115784139
49999995.0933498618
49999994.8836178114
49999997.9886450427
49999996.2295945657
49999998.0441679807
49999995.8618392846
49999996.7392814076
49999996.2061849361
49999996.8127210472
49999997.1296632283
49999998.4672184243
...

result:

ok 100000 numbers

Test #15:

score: 0
Accepted
time: 2687ms
memory: 30668kb

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:

49999998.4114884826
49999997.9731765491
49999997.2725407361
49999998.4609082007
49999994.7726248631
49999996.2591437467
49999997.4391602003
49999997.4595152484
49999994.9463549853
49999996.9207552870
49999997.9735086032
49999996.5709999078
49999996.1017815344
49999997.6848153128
49999995.7377748194
...

result:

ok 100000 numbers

Test #16:

score: 0
Accepted
time: 3031ms
memory: 28944kb

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: 3487ms
memory: 28820kb

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: 3003ms
memory: 31080kb

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: 3266ms
memory: 31564kb

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: 3498ms
memory: 30288kb

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: 3075ms
memory: 30248kb

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: 3002ms
memory: 30524kb

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: 2943ms
memory: 29900kb

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: 2999ms
memory: 29892kb

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: 2642ms
memory: 30260kb

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: 2966ms
memory: 29080kb

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: 3415ms
memory: 28868kb

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:

49999997.4571804445
49999998.4627793917
49999997.1012831272
49999996.8661267463
49999998.6305340222
49999998.5050832598
49999996.2101661278
49999998.6642196312
49999997.4219625144
49999996.6097953529
49999997.2465502875
49999997.5784507015
49999997.7963023625
49999996.7176688653
49999998.5363129047
...

result:

ok 100000 numbers

Test #28:

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

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:

49999997.2281586992
49999997.3025419674
49999996.6710480845
49999996.7132198505
49999998.7399825526
50000000.5315516597
49999998.0506880440
49999998.9604979678
49999996.7553592107
49999997.1424608377
49999998.7725008478
49999997.5903435250
49999998.3012374512
49999999.1442935974
49999997.1038764379
...

result:

ok 100000 numbers

Test #29:

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

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:

49999996.8124151280
49999996.7088924272
49999997.6572201374
49999997.0251825251
49999997.5584498117
49999997.9676561649
49999998.1619126608
49999996.5120547797
49999998.4548825087
49999998.2111204075
49999998.4433880100
49999997.0462427771
49999997.1573696596
49999997.0651829779
49999995.5362256137
...

result:

ok 100000 numbers

Test #30:

score: 0
Accepted
time: 3078ms
memory: 31192kb

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:

49999997.0242636219
49999996.4351697949
49999997.5472669976
49999996.4184565740
49999998.7878663446
49999997.8148425174
49999998.1209330582
49999996.1151277519
49999996.8872683443
49999996.1102720128
49999997.6365981970
49999998.0198364671
49999998.7855395929
49999998.6437689914
49999996.0682024158
...

result:

ok 100000 numbers

Test #31:

score: 0
Accepted
time: 3083ms
memory: 30700kb

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:

49999996.0831308637
49999996.4655374477
49999998.4432053235
49999995.6520978698
49999998.1852533965
49999998.4148445374
49999999.0013581327
49999997.2984745646
49999997.1851978291
49999999.0488718601
49999997.2643068664
49999996.6181674743
49999996.5855972062
49999997.8302103618
49999997.6317784903
...

result:

ok 100000 numbers

Test #32:

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

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:

ok 100000 numbers

Test #33:

score: -100
Time Limit Exceeded

input:

100000
-82922797 55795521
98806631 15264719
27227855 96151671
90640250 -42064680
97570886 21814297
11561464 99312553
-63044255 -77522636
75253645 65715048
-46471655 -88525692
-74788283 66304581
59047518 -80664807
99509005 9753002
6599999 -99699054
-57520499 -81692754
-94724230 -32037998
-91266303 -4...

output:

49951008.8752196898
49952120.1151771756
49951313.8975321696
49951522.6341236542
49951493.4673221721
49951417.8990497972
49951239.5873102925
49950786.0584494720
49951126.6194569922
49951635.2534672451
49951599.4435538328
49952120.2602650853
49951396.9518224784
49951843.5781770995
49951084.2984792269
...

result: