QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#338325#5570. Epidemic Escapeucup-team1198#TL 3586ms32116kbC++207.4kb2024-02-25 20:35:182024-02-25 20:35:18

Judging History

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

  • [2024-02-25 20:35:18]
  • 评测
  • 测评结果:TL
  • 用时:3586ms
  • 内存:32116kb
  • [2024-02-25 20:35:18]
  • 提交

answer

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

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(20);
    
    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 = rnd() % 5 + 1;*/
        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 + 1; ++i) {
            auto res = get_bst(dir, hulls[i], k - i + 1);
            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 /= hypotl(dir.x, 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: 3888kb

input:

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

output:

8.70025542409212514910
3.22601956225725357806

result:

ok 2 numbers

Test #2:

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

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.16776296812470206979
26.16295090390225840452
5.46148832016331211474
6.36396103067892771965
-1
5.28940822164257382640
3.72677996249964949395
4.60977222864644365502
2.92944237920141117263
4.76172894020648764662

result:

ok 10 numbers

Test #3:

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

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.00000000000000000043
5.13052765800816796063
-1
-1
-1
3.53553390593273762191
2.23606797749978969641
11.98540779448075350392
15.32064692570852969429
3.53553390593273762191
2.46274009132032641804
4.52769256906870831312
3.76299830587259233751
15.32064692570852969429
2.98142396999971959507
5.6217035047...

result:

ok 20 numbers

Test #4:

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

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.75867886875729206170
29.57140599786168911646
24.62214450449026180434
27.77174565473063996141
26.67836671289650964101
24.42370246047215748622
28.89334819639630475355
29.77616955775845975461
31.94036297051516979685
27.21490160237785782549
31.72809504574849995447
27.07116055168118726008
25.299110030...

result:

ok 100 numbers

Test #5:

score: 0
Accepted
time: 163ms
memory: 5700kb

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.15491700461674147850
2.16726593574273330815
2.06764308549470956318
2.11184197874980137993
2.11184197874980137993
2.11184197874980137972
2.12498727861040508482
2.12132034355964257336
2.02758751009940656304
2.09288228288167225326
2.14153721439180225162
2.06155281280883027483
2.15491700461674147850
2...

result:

ok 10000 numbers

Test #6:

score: 0
Accepted
time: 206ms
memory: 5596kb

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.30237593728341415067
481.66271198905148287484
792.18507560181845739145
579.95426184927108798073
807.70944626782363262585
242.59217548455710165844
882.26751476671612905989
530.78078025974181591851
664.18217596104036642979
796.36073976751668951346
662.70716789865296925122
639.07261927874407186900
...

result:

ok 10000 numbers

Test #7:

score: 0
Accepted
time: 2016ms
memory: 29196kb

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.49777633241246355134
1193.96022874512525269175
1171.24272618705977566655
1856.28903629903064309570
2681.88294585397396074811
1170.87074083629297549525
1128.36147157215269765107
1855.87833798919723571341
3518.32414797021084296169
1541.78600821544994825540
1515.01512231648064077394
1124.406566046...

result:

ok 100000 numbers

Test #8:

score: 0
Accepted
time: 2505ms
memory: 28920kb

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:

50000000.75722037423838628456
49999995.90040911236428655684
49999998.28364718900047591887
49999995.30546740023055463098
50000000.43184847111842827871
50000000.17242530638395692222
49999996.27292771068823640235
50000000.77632329781044973060
49999996.66118371554694022052
49999997.44037873152774409391
...

result:

ok 100000 numbers

Test #9:

score: 0
Accepted
time: 2453ms
memory: 29000kb

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:

50000001.20026518381564528681
49999996.58714230447367299348
49999996.78157523551635676995
49999998.48554099997636512853
50000002.27364296761152218096
49999997.47261448338758782484
49999994.86781723578314995393
49999996.47133426529035205022
49999996.29124804206730914302
49999997.24230763825107715093
...

result:

ok 100000 numbers

Test #10:

score: 0
Accepted
time: 2536ms
memory: 30096kb

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.77159081483478075825
49999995.43577723267662804574
50000002.50569466288288822398
49999995.74680647960121859796
50000002.33851895939369569533
49999996.06714140293479431421
49999995.85126753839358570985
49999994.54023016176506644115
49999994.61797808467963477597
49999995.70534621365368366241
...

result:

ok 100000 numbers

Test #11:

score: 0
Accepted
time: 2283ms
memory: 29248kb

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.19806852666806662455
49999995.17420686882178415544
49999997.44963262832607142627
50000001.08113966829114360735
49999998.61770883033386780880
49999996.61076225926080951467
49999996.63799070696768467315
49999998.99541351890366058797
49999999.03882681636241613887
49999995.66283840977848740295
...

result:

ok 100000 numbers

Test #12:

score: 0
Accepted
time: 2223ms
memory: 28708kb

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.88006099844278651290
49999996.56664605913829291239
49999996.23561363217231701128
49999994.82342861196957528591
49999996.57531662177279940806
49999994.97579745765324332751
50000000.39017711137057631277
49999998.29419431447240640409
50000003.57034249382195412181
49999998.34136389142804546282
...

result:

ok 100000 numbers

Test #13:

score: 0
Accepted
time: 2753ms
memory: 28428kb

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.30562379878028878011
49950587.93211838142087799497
49950271.25519748192527913488
49950284.22509544752028887160
49950441.67093761177602573298
49950141.28468223017262062058
49950288.37664972553102415986
49950469.21839078074117423967
49950744.14640286607755115256
49950688.23120256834590691142
...

result:

ok 100000 numbers

Test #14:

score: 0
Accepted
time: 3246ms
memory: 29852kb

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.01973910689048352651
49999997.14979835446865763515
50000002.17568691684937220998
50000004.06798062460802611895
50000004.85049656912087812088
49999995.94901876136282226071
49999999.09299009418464265764
49999999.47611621229953016154
49999999.89946862709621200338
49999996.06468691439658869058
...

result:

ok 100000 numbers

Test #15:

score: 0
Accepted
time: 3178ms
memory: 30320kb

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:

50000003.79926228878684923984
50000004.93094880570060922764
49999998.04402234447479713708
49999999.26557012314515304752
49999994.77262486312247347087
50000001.81673957270686514676
49999997.43916020027245394886
50000002.92595170583444996737
50000007.64155358008429175243
49999999.51899096305714920163
...

result:

ok 100000 numbers

Test #16:

score: 0
Accepted
time: 3099ms
memory: 30164kb

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.87647377432222128846
49951660.77597273051287629642
49951740.41140560552230454050
49951465.46383040276850806549
49950200.25774712361453566700
49950954.51307898539744201116
49951162.32040784935816191137
49950823.99872299964044941589
49951011.43646243672264972702
49951169.76144168762766639702
...

result:

ok 100000 numbers

Test #17:

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

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.43424631681045866571
49950523.64291778929327847436
49951727.03686738484975649044
49950791.71970917270300560631
49952062.18466975998308043927
49951220.30371584850945509970
49950723.94345442857229500078
49951030.27516904035292100161
49951362.77555942379694897681
49951028.05088762303057592362
...

result:

ok 100000 numbers

Test #18:

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

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.60713418622253811918
49503940.16600041991841862909
49500902.05745306875178357586
49502328.80017626681728870608
49504050.88994257494050543755
49503864.71132244031468871981
49502762.95022318491464830004
49505338.45438240512885386124
49503140.18289404054303304292
49508220.51364764642494264990
...

result:

ok 100000 numbers

Test #19:

score: 0
Accepted
time: 3361ms
memory: 29996kb

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.25224621044253581204
49505902.95302840996373561211
49506391.35179893389067729004
49501384.86199980963647249155
49501974.53753678752036648802
49503956.29212748857389669865
49506260.84844049164894386195
49507848.95784313580952584743
49507844.19772498357633594424
49507646.91598790789430495352
...

result:

ok 100000 numbers

Test #20:

score: 0
Accepted
time: 3578ms
memory: 30220kb

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.70220437647003564052
49504111.90001564027261338197
49506914.00372836190217640251
49504020.38416256531490944326
49500748.18082902173773618415
49509533.28161756649569724686
49504423.65149284744620672427
49503519.12649732064164709300
49507687.16623492304279352538
49501887.84515729121267213486
...

result:

ok 100000 numbers

Test #21:

score: 0
Accepted
time: 3165ms
memory: 32116kb

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.91140013068797998130
49507188.36982793376591871493
49504015.58684922200336586684
49502226.25513368642714340240
49511712.37916546835549524985
49508088.37256575332867214456
49508038.47216066546752699651
49511153.94594372667779680341
49503445.76442513304573367350
49505408.24223563592386199161
...

result:

ok 100000 numbers

Test #22:

score: 0
Accepted
time: 3088ms
memory: 29840kb

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.13722390805924078450
45027842.88181356272252742201
45013570.76497086887320620008
45012430.84675867895930423401
45008268.50800205787891172804
45035953.62510269844642607495
45011940.32668644070508889854
45033497.63786872338459943421
45035993.03178093109454493970
45018438.55247308432444697246
...

result:

ok 100000 numbers

Test #23:

score: 0
Accepted
time: 3039ms
memory: 31284kb

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.38842729735915781930
45009163.60652219889016123489
45033436.39317698411832679994
45019451.02397266065963776782
45022200.75043971279592369683
45014848.45843437976873246953
45024066.21682186085672583431
45004916.90905756798747461289
45009051.61571304868994047865
45011633.81192500219913199544
...

result:

ok 100000 numbers

Test #24:

score: 0
Accepted
time: 3072ms
memory: 28900kb

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.36641709442483261228
45049419.11604576809259015135
45013923.51296881854432285763
45018139.64885055125705548562
45036905.81273686467466177419
45014915.92618466516069020145
45021998.41649369706647121347
45005546.41905103952376521192
45013393.31874032204723334871
45031474.26175472207251004875
...

result:

ok 100000 numbers

Test #25:

score: 0
Accepted
time: 2767ms
memory: 29580kb

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.83566114364293753169
45013616.11356252005862188525
45048543.60614620956403086893
45027729.03306478201920981519
45013317.49851936619597836398
45020005.92026786229325807653
45013214.45326151939298142679
45017977.19282532306533539668
45015065.22138667024046299048
45019880.16614929549905355088
...

result:

ok 100000 numbers

Test #26:

score: 0
Accepted
time: 3069ms
memory: 31116kb

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.00836193299983278848
45031012.68375462417316157371
45051159.92675329238772974350
45057523.94390060050500323996
45021248.93839351287897443399
45034531.52225729142082855105
45010861.90440167927590664476
45036940.66625836228195112199
45011332.88730371226120041683
45014214.38335442236348171718
...

result:

ok 100000 numbers

Test #27:

score: -100
Time Limit Exceeded

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.67371651414941879921
50000008.14289628739425097592
49999997.95607159681821940467
50000000.22731511348683852702
50000001.10161455503111938015
50000002.96438538809161400422
50000003.17249695557984523475
50000000.26405478567539830692
49999998.58670662751319468953
49999999.43837164171054610051
...

result: