QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#55290#1343. Zombie LandckisekiTL 276ms15200kbC++5.1kb2022-10-13 00:34:422022-10-13 00:34:45

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-13 00:34:45]
  • Judged
  • Verdict: TL
  • Time: 276ms
  • Memory: 15200kb
  • [2022-10-13 00:34:42]
  • Submitted

answer

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

const long double eps = 1e-10;

using PT = complex<int64_t>;
using lld = int64_t;
int sgn(lld x) {
    return (x > 0) - (x < 0);
}
lld cross(PT a, PT b) {
    return imag(conj(a) * b);
}
int ori(PT a, PT b, PT c) {
    return sgn(cross(b - a, c - a));
}

#define above(P, Vi, Vj) (ori(P, Vi, Vj) > 0)
#define below(P, Vi, Vj) (ori(P, Vi, Vj) < 0)

int Rtan(PT P, int n, PT *V) {
    if (n == 1)
        return 0;
    int a, b, c;
    int upA, dnC;
    if (below(P, V[1], V[0]) && !above(P, V[n-1], V[0]))
        return 0;
    for (a = 0, b = n;;) {
        c = (a + b) / 2;
        dnC = below(P, V[c+1], V[c]);
        if (dnC && !above(P, V[c-1], V[c]))
            return c;
        upA = above(P, V[a+1], V[a]);
        if (upA) {
            if (dnC) {
                b = c;
            } else {
                if (above(P, V[a], V[c]))
                    b = c;
                else
                    a = c;
            }
        } else {
            if (!dnC) {
                a = c;
            } else {
                if (below(P, V[a], V[c]))
                    b = c;
                else
                    a = c;
            }
        }
    }
}

int Ltan(PT P, int n, PT *V) {
    if (n == 1)
        return 0;
    int a, b, c;
    int dnA, dnC;
    if (above(P, V[n - 1], V[0]) && !below(P, V[1], V[0]))
        return 0;
    for (a = 0, b = n;;) {
        c = (a + b) / 2;
        dnC = below(P, V[c + 1], V[c]);
        if (above(P, V[c - 1], V[c]) && !dnC)
            return c;
        dnA = below(P, V[a + 1], V[a]);
        if (dnA) {
            if (!dnC) {
                b = c;
            } else {
                if (below(P, V[a], V[c]))
                    b = c;
                else
                    a = c;
            }
        } else {
            if (dnC) {
                a = c;
            } else {
                if (above(P, V[a], V[c]))
                    b = c;
                else
                    a = c;
            }
        }
    }
}

#define MP make_pair
void build(vector<PT> &dots) {
    if (dots.size() <= 1) return;
    sort(dots.begin(), dots.end(), [](PT a, PT b) {
        return MP(real(a), imag(a)) < MP(real(b), imag(b));
    });
    vector<PT> ans(1, dots[0]);
    for (int ct = 0; ct < 2; ++ct, reverse(dots.begin(), dots.end())) {
        for (int i = 1, t = ans.size(); i < dots.size(); i++) {
            while (ans.size() > t && ori(
                        ans[ans.size() - 2], ans.back(), dots[i]) <= 0)
                ans.pop_back();
            ans.emplace_back(dots[i]);
        }
    }
    ans.pop_back(), ans.swap(dots);
}

long double slope(PT a, PT b) {
    if (real(a) == real(b)) {
        return -1e9;
    } else {
        return -(imag(a) - imag(b)) / (long double)(real(a) - real(b));
    }
}

int main() {
    // freopen("i.in", "r", stdin);
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    int xz, vz;
    cin >> xz >> vz;

    vector<tuple<int,int,int>> L, R;
    for (int i = 0; i < n; i++) {
        int x, v;
        cin >> x >> v;
        v -= vz;
        if (x < xz) {
            L.emplace_back(x, v, i);
            // cerr << "L " << v << ' ' << x << endl;
        } else if (x > xz) {
            R.emplace_back(x, v, i);
            // cerr << "R " << v << ' ' << x << endl;
        } else
            __builtin_unreachable();
    }

    // cerr << fixed << setprecision(3);

    vector<long double> ans(n, -1);
    {
        vector<PT> cv;
        for (auto [x, v, id]: L) {
            cv.emplace_back(v, x);
        }
        cv.emplace_back(0, xz);
        build(cv);
        cv.emplace_back(cv.front());
        for (auto [x, v, id]: R) {
            // for (int j = 0; j < cv.size(); j++) {
            for (int j: {
                Ltan({v, x}, cv.size()-1, cv.data()),
                Rtan({v, x}, cv.size()-1, cv.data())
            }) {
                long double s = slope({v,x}, cv[j]);
                if (s < 0) continue;
                if (ans[id] < -eps || ans[id] > s)
                    ans[id] = s;
            }
        }
    }
    {
        vector<PT> cv;
        for (auto [x, v, id]: R) {
            cv.emplace_back(v, x);
        }
        cv.emplace_back(0, xz);
        build(cv);
        cv.emplace_back(cv.front());
        for (auto [x, v, id]: L) {
            // for (int j = 0; j < cv.size(); j++) {
            for (int j: {
                Ltan({v, x}, cv.size()-1, cv.data()),
                Rtan({v, x}, cv.size()-1, cv.data())
            }) {
                long double s = slope({v,x}, cv[j]);
                if (s < 0) {
                    continue;
                }
                if (ans[id] < -eps || ans[id] > s)
                    ans[id] = s;
            }
        }
    }

    cout << fixed << setprecision(15);
    for (int i = 0; i < n; i++) {
        if (ans[i] < -eps) {
            cout << -1 << '\n';
        } else {
            cout << ans[i] << '\n';
        }
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3768kb

input:

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

output:

3.666666666666667
2.000000000000000
-1
6.000000000000000
0.750000000000000
2.000000000000000

result:

ok 6 numbers

Test #2:

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

input:

5
31415 -926
5358 979
323846 26
-433832 7950
288 -4
-1971 -69

output:

13.678215223097113
95.618122160524987
52.416291122127084
33.760303687635575
38.956826137689615

result:

ok 5 numbers

Test #3:

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

input:

972
98740224 301565350
897445571 19067267
-528259301 772813962
88724382 432443246
668138287 561147750
-111697007 795680328
716395194 388109596
-289144978 72929322
-935429651 690324478
632898250 -359347321
-388094843 -753263424
416481084 91553128
460683861 290773570
445572029 -788653120
-239712630 23...

output:

0.855538050950053
0.373207830312455
0.011835082179113
1.450834985624153
0.127333455215852
1.093110811464487
0.395160591301566
0.641783244542102
0.407945345592419
2.445301045525544
0.370335430246002
0.547955469015428
0.200072536958072
0.298295898674546
0.237186774358005
0.701505526702360
2.3840345817...

result:

ok 972 numbers

Test #4:

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

input:

259
752382432 741617032
-250270272 196077394
54972511 -207249508
-307820783 -496822
-111301002 30287969
-554984572 88923386
339153990 -105509849
-516393652 296569551
-639995187 73270418
126116221 82234518
833021455 -513535638
-659275813 -761684056
855148226 534782501
-895143984 74143074
-639832645 1...

output:

0.975180346548473
1.100877824637191
1.249851822586702
0.999380837458391
1.385681096572518
0.606922434663169
1.114761551511262
1.494426169515398
0.707175044716539
0.061654532647334
9.534592057995221
0.255371525224389
1.752904749205087
1.407765212939430
1.082905366428994
0.925482415724938
0.5440032068...

result:

ok 259 numbers

Test #5:

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

input:

259
-239521039 -17174750
-28208238 273288492
-262032452 23998023
-61550699 -987581973
2011476 64785627
506746250 -524302272
236281620 -439651597
112812321 -127351173
661550726 -373795229
520592707 14606789
-407177660 -355703473
208286492 -808497964
115090879 567927785
-144929466 296145103
99561934 7...

output:

0.395547978852739
0.152227590935776
0.099866800902961
0.325609341059924
0.558528200294163
0.381555786311965
0.376967877414078
0.747274914533836
0.917470162942614
0.546983258648617
0.277427608145764
1.232935483654100
0.186771826772175
0.465530215798841
0.402286946568014
9.703374046849641
0.8730475492...

result:

ok 259 numbers

Test #6:

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

input:

449
-612729477 83287736
216626656 870884456
55962361 -806449489
-110510397 -600090426
-97868933 646268222
-215680276 -939993977
998032744 -946549522
-797455786 -518392076
481499951 -334510546
212968104 -885110705
230852131 -26556218
-497222554 -347474765
30083868 -263841324
571546796 -447627402
-651...

output:

7.247618995091625
0.387687720721996
0.333276419845386
1.581772759137209
0.220035803555445
0.846322203452318
0.444531372109067
0.847417225307409
0.455188028342125
0.857576163484658
0.106935575869052
0.534928554322927
0.843373083144122
0.064059667596824
0.634647779225220
0.564852724441405
3.6614683324...

result:

ok 449 numbers

Test #7:

score: 0
Accepted
time: 3ms
memory: 3792kb

input:

517
312396635 835807552
836049671 -365330548
-478329286 -13614133
925695145 -81767313
-695773681 952104867
904596597 -897413272
-146550641 535824901
750199768 -778382942
118295875 333791214
-175655702 972577908
-833081270 181896163
-214239604 264865187
546088727 -702688220
-853243884 -912569756
6608...

output:

0.423685472572115
1.020125415433794
0.619528098904705
0.592932326400813
0.340536876595865
0.373934581737468
0.271221478894423
0.212889977109741
0.300093395252861
1.171364857001022
0.526214709200495
0.151896479829910
31.103440377167749
0.283873770506667
1.761893061795690
0.313941397845133
0.057669855...

result:

ok 517 numbers

Test #8:

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

input:

693
629151502 295918477
-616892310 696727474
48705044 -815840765
447233060 -411113265
-691083808 988324904
-256578149 306794729
-686628838 -75136980
195027198 543025801
-102991986 -417841893
-209687785 -872356544
444638352 -719223204
-186025638 938388900
-51414040 567834866
342129301 561300204
-7956...

output:

0.808079455862049
4.720603728038302
0.423657058389667
0.720281950978805
0.769007005202668
1.667688770475053
0.314563865380703
1.645241415380027
9.550937105860242
1.427820160790967
0.458054556692593
0.482818021723857
0.206295823445627
1.129159828855146
1.033677241236941
5.819048013393209
2.1739276674...

result:

ok 693 numbers

Test #9:

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

input:

313
917008461 -906615562
641196337 37274959
740530413 -476468996
645591586 -332815726
758084387 -573984824
596558953 -434175831
115895393 -799543133
-109378856 320378868
-175337574 -882455278
530091206 649606296
818414694 747484951
875722452 -636757835
612908343 533089510
-877437920 -649973078
93741...

output:

0.278742520830784
0.364463248479121
0.429433956605592
0.407884687879026
0.596494735255854
4.299014770654642
0.792008178479044
10.422369238744950
0.242366611992520
0.059605668594578
0.146029294485339
0.206491511157410
5.334716449964769
0.049866310224051
0.234035359525905
1.234445723972986
0.453136040...

result:

ok 313 numbers

Test #10:

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

input:

210
215238211 -31335938
405713900 377969062
359517473 914510356
-12564907 -662794228
655642045 437220266
-157797997 607838893
172130325 100900457
-107545120 579497988
130937694 578158720
-269202122 777971134
870491026 -715643223
-745057909 -129866869
-202609023 813073934
-915998802 91888388
46391823...

output:

0.448375308240699
2.993645710032585
0.940812634158027
0.947772452312319
0.273675073257839
0.094529212210843
0.246184063379864
0.091989738549818
0.310849135371370
0.433390657526814
1.217101131632584
0.267292813561127
1.123588635535778
0.183572503106505
0.146558863693676
2.076463409969939
0.3121086418...

result:

ok 210 numbers

Test #11:

score: 0
Accepted
time: 3ms
memory: 3752kb

input:

818
876550168 576707152
-518771879 -267634574
-954556654 -669698257
39954799 -922437716
531677243 953193289
-134094433 -962014935
-251440954 -626274080
60281296 -885162935
-56054845 411669772
-252344579 743459521
143314578 -151738075
202450333 -826054754
910810678 -311095703
-697291633 -770724756
-1...

output:

2.099025918442827
6.218446215226137
16.183216650546918
0.203573257348481
60.595452049715518
3.470074950744703
9.632770595536301
0.737314776102688
0.707827638135135
1.006414998307843
5.021350399630187
0.038590222825990
7.988049293144702
0.915566827896744
0.743278101335533
0.689216960639901
8.17631606...

result:

ok 818 numbers

Test #12:

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

input:

267
-294506756 -193668172
-250609952 88358868
-926678876 660710497
335837379 -283642133
-981468927 -157245064
379531021 -20632943
267151333 -281111227
63421851 -418152451
356094548 -758864950
-66080068 -788871585
-444036769 -585601987
532194328 624340358
-154035561 928129897
-12644223 502171650
9400...

output:

0.108812275163584
0.401869692167095
0.545288691222903
0.870053088516004
0.734700263302417
0.491371660479554
0.295706664302449
0.406896119270906
0.159536716113298
0.448477952045586
2.561979751897105
4.917759746194379
0.717345762833924
0.936800392610985
0.122470289516819
0.592171902245709
0.8495172862...

result:

ok 267 numbers

Test #13:

score: 0
Accepted
time: 113ms
memory: 13144kb

input:

141458
-943448502 -452767471
817779662 -19264034
162008856 340294557
648357734 -3592443
757048168 25507919
208739377 820628452
622724656 940628216
48209937 -701890182
826415454 -210140744
-552537840 907219232
672390512 -652105046
-715817725 818502234
-904132692 385779467
997872329 -219660069
-171771...

output:

1.741036146527705
1.695432600441978
1.598414972661594
1.758832522434034
6.600821238279022
26.993675281710344
0.585780868112260
1.472003777330880
4.515071165423901
0.982921683901348
1.311172807320711
0.066605621175643
1.601836228232266
0.675746698030412
2.115178240740645
0.396658890737360
0.715891846...

result:

ok 141458 numbers

Test #14:

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

input:

28540
-735192790 81113103
980834912 -502512836
823934433 690164993
-392140847 939781319
835069435 887034496
-11103637 629371107
155827223 719209606
485737166 -481197099
-880261600 595209718
-744448148 35089966
206879579 -177044655
-184779896 -378004741
-812272688 343020578
661458093 -908944243
-6305...

output:

1.146387345376889
5.091219968617539
6.048715790553402
14.308111650155116
1.977790515996068
3.218387563419337
0.827982525182818
0.093665165640699
0.009804937014702
0.804963872537877
0.402471139839079
0.059584585062674
0.734355840302278
0.127152290191961
0.399644455992547
0.454564144495911
2.505669709...

result:

ok 28540 numbers

Test #15:

score: 0
Accepted
time: 147ms
memory: 11812kb

input:

189217
97334466 -343324026
-442234575 758603741
-333938447 450224695
-263614720 -790599140
-890243472 961176720
-328006976 246592225
-105447419 755181969
965506346 453423668
986914920 -617160390
-464495560 -17199756
877330089 347574165
258044627 518735377
732635111 -230085526
923925355 -792822568
41...

output:

0.309206504713177
0.300225530922652
1.791303736057753
0.506615975001855
0.344832781826660
0.116938387522693
1.593076928823256
0.551411651516984
0.578412506538383
1.199218225252311
0.338199941936465
0.518197871119828
0.462229274787012
0.255714112314213
0.363801222608999
0.591708504445998
0.9039853012...

result:

ok 189217 numbers

Test #16:

score: 0
Accepted
time: 130ms
memory: 11104kb

input:

164300
485658262 419578482
-502940892 -945916443
678915904 -755506847
-376986279 448395043
13354348 -996488366
-270865353 688380322
-700611843 -198048964
-442108444 -5953728
721653448 768715719
308055697 -692734051
413185986 250160422
-85807535 -585215004
430052565 252646083
-517841570 861306548
114...

output:

19.081065039576761
0.111338521074793
0.598575319775865
167.593788039645124
0.450045559062327
1.492164162236221
0.940001330195985
1.041938831129595
0.591952207161888
0.058511458588265
1.401264565238488
0.044856869810844
0.541254823955683
1.787409646669371
0.421567267718996
2.367754480443696
2.4932281...

result:

ok 164300 numbers

Test #17:

score: 0
Accepted
time: 102ms
memory: 9912kb

input:

125619
816774008 -90826543
811004219 457288098
332829329 -594705600
-83095933 754019962
-208025963 -4950513
150079441 283172520
-435954434 39744648
-506457333 -638276891
488512726 -386830383
490240803 949202939
946819581 -885726699
897718538 -85760811
592557123 -440811992
891689852 129725120
-766486...

output:

0.004584535162530
1.201481171284377
0.514404524137134
1.032773566391245
0.521447117007690
1.207741584069997
3.672447215047967
0.539310813862372
0.168599968712513
0.069894359966221
0.076285680134462
0.405099550499790
0.088527554051965
1.219778435763439
0.619953996080231
1.429148366923105
4.6431603733...

result:

ok 125619 numbers

Test #18:

score: 0
Accepted
time: 185ms
memory: 12196kb

input:

199207
58608778 899029538
-104717827 200019693
-32776752 178322972
-501587420 856278500
28913723 -254803559
997421016 669106430
-417871365 493082679
-179100685 794548712
421298972 299030092
464316278 -458136567
954070573 412915502
883619362 -174208443
-786242074 814199462
-157410352 344418157
735177...

output:

0.138722769887697
0.079644929422093
0.304209713326795
0.041956363673522
2.880396073856713
0.322239275220334
0.134192920781537
0.522580571009739
0.279916757438828
1.539820899371393
0.706452923190533
0.468914529043252
0.163165906834771
0.524397807251844
0.300856112801735
0.496546001562662
0.6424740458...

result:

ok 199207 numbers

Test #19:

score: 0
Accepted
time: 125ms
memory: 14152kb

input:

164806
961321411 418704190
191446659 -27039796
-464672499 833374152
115008000 -471989037
397524246 -330416931
894002833 -488053094
329180568 -385926453
974196337 -288420413
-169960840 558580731
-992681915 -679780674
433330580 -311372754
555688384 8243484
-560144111 -194462146
-122537229 362225477
49...

output:

0.795443860710926
0.780002306127680
1.612357950090163
0.848169837348947
0.137903474996613
1.036499924256915
0.010464713682804
0.728395509770069
6.134531431687967
0.772586615235601
0.405885599995468
1.895417407058267
0.798636432432040
0.553277073383533
1.738690402543579
0.857234382368890
1.0653865565...

result:

ok 164806 numbers

Test #20:

score: 0
Accepted
time: 25ms
memory: 4988kb

input:

36006
474728818 109562890
362653856 -745035243
-175037930 179028396
-841501239 -388853520
-743504875 183385424
-857561685 213008483
-104532818 4702930
623992369 -188545500
-463764255 401810176
483586216 -704204407
163405849 787882243
214096125 -215739979
951950972 -424870138
212815375 119574421
-759...

output:

0.460515194226026
0.555797330737141
2.168130523364460
1.034948425313264
1.103817378241655
0.582111644225608
0.131832989820332
0.673605401716824
0.005587652873283
0.176793389058534
0.338822861549131
0.341027052016623
0.238306102724997
11.466508246133405
20.116918100810969
0.607540328623847
0.15032838...

result:

ok 36006 numbers

Test #21:

score: 0
Accepted
time: 140ms
memory: 14408kb

input:

180301
717556654 259485243
147256170 -147541416
905309145 908433659
-295293340 897690534
-161137682 963284292
615177765 -595083077
-291174108 977556560
-50607538 -112005963
768575486 832864290
783759662 95842227
-195487419 -181039653
979575296 666587518
-598121196 39479716
287098259 -317095281
57873...

output:

0.674480330525600
2.219666938995624
0.535935862595466
0.449546798743092
0.260855771926084
0.512167186662527
0.871070239557337
0.355549005734870
0.078690615097406
1.122457409896674
0.822138111161820
1.272170929182291
0.636978625773755
0.099961205032902
0.377976133603906
2.612439629765996
0.3639927213...

result:

ok 180301 numbers

Test #22:

score: 0
Accepted
time: 67ms
memory: 8728kb

input:

79965
-732104648 -869951410
694639834 -520477131
-873777433 -946012830
-762131454 372304580
807718873 -934739059
-565466263 663876591
300523572 611691242
-473406430 909994032
-731431762 624366066
724251124 594259629
991213603 -949320671
247154158 -915880587
114815202 -567997008
780887358 752956830
-...

output:

0.941449745928100
3.027429296679424
0.022434360913665
0.798311611996117
0.509708690732063
2.671645806141507
2.927653904255929
0.005304077761054
3.601312129514808
0.886474884127610
0.513573572673816
0.543118489228919
6.144520061452446
0.236920807436715
0.546604686116970
0.364992008164299
0.9742659078...

result:

ok 79965 numbers

Test #23:

score: 0
Accepted
time: 216ms
memory: 13976kb

input:

198318
-191669615 294947791
-119523266 75482204
-388183631 655425794
-257388994 503179005
-191381044 280954364
-231193937 456317304
-110250348 61831503
-167038765 166585260
-40868542 -22135647
-182193974 215141250
-626306072 785000026
-153029202 134255653
-129379809 91011504
-171068222 177493666
297...

output:

0.272983977586335
0.450884369844585
0.260774546251577
0.016980346722757
0.202264418401418
0.290006886387838
0.159234500894738
0.394716096180746
0.098378224554258
0.713559693750505
0.199694313681937
0.253633388416359
0.145529634910143
0.781950397426050
0.462978931397397
0.100240458063372
0.2462604608...

result:

ok 198318 numbers

Test #24:

score: 0
Accepted
time: 195ms
memory: 14036kb

input:

198628
-106521361 -448556420
-418240089 -2881757
-200629197 -198539490
-338679538 -57007070
-385564543 -22811266
241303784 -911274945
61726653 -781662143
-166459338 -248875955
37561219 -756793961
-560724276 46020876
-249667868 -140278108
-479597518 25778085
-85129944 -567061319
1253843 -715113956
13...

output:

0.576630582716035
0.312392638458618
0.491477936089863
0.541939460815950
0.615546441065634
0.417983535741188
0.249144257968952
0.386855119730820
0.737271004671511
0.385258957509706
0.642981029540613
0.149415368779892
0.334634882487617
0.506931890022213
0.410532627260635
0.455033987090101
0.2562997320...

result:

ok 198628 numbers

Test #25:

score: 0
Accepted
time: 183ms
memory: 13944kb

input:

198957
-254086118 -175277458
-223742595 -316655154
-248929424 -233404418
-361575583 92693059
-484505856 215546395
86236692 -634900445
107560858 -644290557
-172560805 -407435112
-640310966 304550912
-67420954 -526714994
-334110963 56028401
-2693991 -581046598
-706899132 320203472
-102654828 -49180319...

output:

0.177130379817969
0.073125060965956
0.333203960726927
0.488768760902212
0.606575826474663
0.629709111937177
0.290245207698194
0.656502882659132
0.439276143463191
0.287504999017932
0.511623985780072
0.734101279094710
0.395647398702443
0.598370414983337
0.446159958512067
0.024510239706539
0.1258468812...

result:

ok 198957 numbers

Test #26:

score: 0
Accepted
time: 192ms
memory: 13856kb

input:

199075
-168317147 -347030106
-216571645 -167450311
-276061257 -78960013
-92385645 -572381147
-578321365 140750361
-435847365 71902205
-128975384 -509247662
-343256185 -5459811
-14371437 -667604028
146531590 -795675346
-547339587 130984308
-199433045 -202680221
-320847097 -28080724
-528384398 1235680...

output:

0.222634647793624
0.332896589913666
0.279018936992565
0.681403021625529
0.527528315487772
0.200827581710013
0.424083216811001
0.397584505255428
0.577556279012278
0.646632732087021
0.178733644984605
0.396001557335298
0.625904442814420
0.149560364748737
0.667190999294076
0.723397640956688
0.7271289182...

result:

ok 199075 numbers

Test #27:

score: 0
Accepted
time: 205ms
memory: 13848kb

input:

198337
-289771326 79901717
-33004142 -330224532
183577438 -415836059
-647497176 548047991
-102909422 -272156297
-448263347 403982222
-289874455 87976902
-296437854 146094762
-301890622 169122253
-777874953 576820690
-576412819 510600539
-718050849 570091251
-660404401 553222314
-472296375 427792749
...

output:

0.518155690214622
0.761468691788125
0.625549364633433
0.440171521839700
0.405056100848465
0.010576001340160
0.083539311262333
0.112604427781077
0.779572883528076
0.549302001098960
0.705451846730250
0.639713554769339
0.434564390150362
0.746207163712609
0.278834150852437
0.129841590676544
0.6990661534...

result:

ok 198337 numbers

Test #28:

score: 0
Accepted
time: 196ms
memory: 13892kb

input:

199381
479553598 408242034
410936431 621916300
478243759 437835530
708162504 19278018
734800934 -1261718
706719737 20450195
11760982 904455528
161033856 857455153
79705497 891185159
23025751 903207817
481173774 375274322
665629524 56513411
472967891 474564225
921280531 -85593665
384928069 659144419
...

output:

0.266145719625939
0.036541437842162
0.486466825794785
0.515369466603132
0.484877419312321
0.752952565273417
0.583346262001054
0.672478471867776
0.739061271003196
0.040687070193331
0.438125699776966
0.082189579570973
0.719913089714342
0.312523825518237
0.531351956237981
0.667305699469123
0.3932676142...

result:

ok 199381 numbers

Test #29:

score: 0
Accepted
time: 175ms
memory: 13844kb

input:

198151
-189196507 -222837022
-379986851 131247404
240827160 -711949189
-288468975 32673965
167131535 -689428166
118948543 -665808349
-187663749 -255184050
62004627 -628705153
303982156 -718235619
262577702 -715461614
-160261893 -361407324
-154069971 -375509848
-189278425 -215456476
-331605395 831209...

output:

0.445738186112867
0.709816248572727
0.321263136018624
0.625740021507465
0.573581545821198
0.039494404704791
0.512576962182183
0.788952149649964
0.736175077549625
0.173353644909443
0.190999324994593
0.009161305442986
0.385011510088568
0.153215049466813
0.713134360853472
0.395695697327495
0.2920557013...

result:

ok 198151 numbers

Test #30:

score: 0
Accepted
time: 203ms
memory: 13944kb

input:

198421
288230264 -358546790
-72277487 108765507
566093950 -782885856
-119942002 124824850
67406886 21973268
281694765 -293575550
-74265492 109572985
403120915 -634054967
487215336 -721361984
292556473 -411105333
715330958 -847814257
547002281 -769722364
385574658 -612104853
178704504 -90240665
73166...

output:

0.631003184228970
0.541487722314466
0.684499278961308
0.480663088448532
0.083571407451035
0.633185114680890
0.346162235864231
0.455025875776473
0.068016820640132
0.705781597548450
0.521080104123637
0.318777140780624
0.338566959508196
0.725316463774253
0.246949901498653
0.543062981097907
0.7377574695...

result:

ok 198421 numbers

Test #31:

score: 0
Accepted
time: 208ms
memory: 13992kb

input:

198151
-331623950 392476621
-631730676 829892552
-321604155 311870932
-258241939 173226177
-148795735 46229212
-148382470 45839122
-299170217 246938840
-333278602 425074226
36076215 -76916277
-330663441 367785770
-395986064 597749035
-525249940 749384375
-601791598 810708476
-223444541 126214783
786...

output:

0.566165481958741
0.103120945910519
0.277638582199697
0.437675186798388
0.438169783623246
0.185056877049849
0.042148116113842
0.640344173529132
0.031870606670544
0.260101687037104
0.449944989140972
0.534333336424021
0.336901016744763
0.688418502070681
0.016804229508177
0.620406432762156
0.1546130313...

result:

ok 198151 numbers

Test #32:

score: 0
Accepted
time: 194ms
memory: 13936kb

input:

198877
90103178 -208664796
-41414341 86262053
490316004 -691507976
445418322 -675233510
93809992 -258285404
163233964 -428145048
-57740987 104054527
-370744637 286077750
175530694 -445895537
129819705 -370644166
79135342 -124056949
-294212127 268786437
366996628 -632209643
-12383561 51611957
2284437...

output:

0.369253686670225
0.673804741982092
0.624048193938221
0.062212645539636
0.276396912286900
0.391520146661440
0.746126531987252
0.298700355634244
0.203511841481028
0.107173339492593
0.656346306016568
0.540375886022088
0.325988475778324
0.379701075309185
0.739170272877784
0.333236568341133
0.3358692040...

result:

ok 198877 numbers

Test #33:

score: 0
Accepted
time: 175ms
memory: 13784kb

input:

199388
255699662 -11542
315052104 -198997064
-463170085 -651125888
670844143 -488130849
-619436191 -650500799
-101834668 -458997766
-226735224 382043202
298526830 -169081519
-532728186 905816561
270226268 -98530812
-580592312 12767477
-110257361 -727077757
138145267 -998551781
296627161 -165301637
2...

output:

0.050499041836110
-1
0.280668790082457
-1
21.465815487174939
0.905331482728635
0.037573879576560
0.763193388096079
0.014065843069430
2.478881732820406
-1
-1
0.036055887248706
0.112211092099702
0.010982795056104
0.014932726537026
0.168606927521354
0.012478980052719
0.620953354130174
1.567173526715610...

result:

ok 199388 numbers

Test #34:

score: 0
Accepted
time: 180ms
memory: 13928kb

input:

199252
111610417 1482
334934011 -384067558
567807977 -495588644
-663156607 890151368
-768560154 863663645
470092020 -468575083
-458998021 285124979
232415756 -282963296
-36599854 403009662
448690895 -458833493
238382881 -289862775
-484268724 -516014562
-156549690 61735923
-155843610 -934744013
42266...

output:

0.162194330949082
0.306218572035471
0.762183452719113
0.872925076887655
0.245135693262303
1.186327806098066
0.094844489549557
0.324163135282921
0.232064329929189
0.098977020525659
-1
1.099727468006532
-1
0.216212243717173
1.112846242190839
1.742187548750230
0.032610782995061
0.060011251095506
-1
0.0...

result:

ok 199252 numbers

Test #35:

score: 0
Accepted
time: 196ms
memory: 13864kb

input:

198349
11936548 13791
16416256 -55131864
-907711390 -49286157
58496939 -175936178
25540970 -95549686
34196753 -121987232
173647223 -327090249
412958404 -482159478
196433420 -349306056
-877743949 -519438747
-91698133 -523268160
135994108 -286571351
-601229440 -820261500
30944650 -112801553
453789422 ...

output:

0.004565751368762
3.049133444889139
0.040221812286273
0.012810653893554
0.020298375267150
0.123110499222440
0.272310393647278
0.138095505179316
-1
-1
0.097498056169902
-1
0.017515418225659
0.298055129964621
-1
0.229951065309926
0.074134414818827
0.004372026297172
0.014810060390493
0.206607009129366
...

result:

ok 198349 numbers

Test #36:

score: 0
Accepted
time: 184ms
memory: 13768kb

input:

198008
349063223 -19573
132499216 556946485
-500663724 760499155
-18757998 -492210521
135694171 -351232042
-553526712 824558503
-221063181 -223409511
809728685 -494800867
114248667 -507171760
-346582818 263741439
-78002085 -376794514
-62482772 397321012
-544963873 -719888662
-450279854 879343006
452...

output:

0.351765785395044
0.929104943543705
195.310084045808208
4.630993914230764
0.923220985300977
3.739433125205270
0.310297525549700
-1
1.413812878008371
7.514685458375586
0.781022109071127
-1
0.790957442229496
0.083032841364332
0.186711308116367
0.313057672819912
1.317846903173989
0.085630707702575
0.07...

result:

ok 198008 numbers

Test #37:

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

input:

199024
490089346 -6563
343246258 781512174
146655693 -824564527
332770008 252511307
123924272 470722265
-362928267 790798514
805062520 -447049657
-154600181 -707038910
-508653456 -442970655
-459911823 237447735
429694019 -501014749
262228562 890284596
729314065 -396846777
576662452 -239588153
146083...

output:

0.180830112177412
-1
0.474722947893253
0.635590415430007
0.906436946629842
0.219467419484865
-1
27.245193412780844
1.848010425169256
-1
0.244658249557388
0.172794635453847
0.070750245611131
1.300538114747394
0.290034834133290
-1
0.051524088382201
0.056307861570328
0.606287069462044
0.318189022053338...

result:

ok 199024 numbers

Test #38:

score: 0
Accepted
time: 175ms
memory: 13864kb

input:

198018
468025540 -9344
885620961 -484703199
-475443022 -969321917
726780925 -408839342
-75351673 49880041
796550137 -451561735
265540838 314157511
869588586 -480491565
576470655 -265893879
-138389724 32252599
121932457 -576148692
292601190 -26591937
252793896 722012065
53291382 -74027638
169763168 -...

output:

0.282239182580977
-1
0.184677595903503
1.736089728211870
0.227313207700318
0.509919611589555
0.272211583909505
0.086776944999885
1.932355091347629
-1
1.121060510207406
0.280414374594951
1.968715142883025
3.613559519455616
0.000354140680081
0.317226912789192
0.272015983232050
2.307872457613413
0.5332...

result:

ok 198018 numbers

Test #39:

score: 0
Accepted
time: 182ms
memory: 13724kb

input:

199784
111436400 -787
111736095 -13798444
567880069 -497704957
113606912 -37763130
115151033 -49547663
22296731 8996336
259106834 -314766259
-227709250 -249745764
366846745 -411262056
-85409422 -471401378
122455003 -85860676
242518422 -296583727
-418597473 7607896
122509516 -86074229
126614187 -1008...

output:

0.000339741642746
0.306029674029523
0.002332463646463
0.003934783896566
0.702516821467772
0.113444586144891
3.129697395523235
0.182159126930530
23.790419073236228
0.010948859812625
0.102218692382770
1.848184115366839
0.010998658113220
0.014708749781158
1.626570218601899
0.449568232313723
1.744447422...

result:

ok 199784 numbers

Test #40:

score: 0
Accepted
time: 182ms
memory: 13780kb

input:

199412
19484465 11807
-952463047 649927291
346290411 -453157951
11870022 213020099
-611371704 58382180
133745191 -274371613
59965854 -163200168
390968283 -473381281
73911797 -189233626
181419140 -326900482
405093146 -478542161
23692752 -52387917
-676429645 -882059139
353246178 -456695451
-960645251 ...

output:

1.156405733249994
0.226639242444908
0.034816719086830
1.871991374487329
0.091163813242891
0.036023801555370
0.253936700335219
0.047208347346918
0.123595663104452
0.262630511190489
0.004302403409088
-1
0.230877226026622
1.078923838386837
0.009843408537554
0.062998512555327
0.229243051975557
0.1160253...

result:

ok 199412 numbers

Test #41:

score: 0
Accepted
time: 184ms
memory: 13844kb

input:

198750
208065152 -29500
-295566360 128861870
214377665 -64198231
-757633846 750845141
668010318 -495251337
549532517 -460557061
505544158 -437025274
-691288264 -172290206
-6653574 982893302
697761564 -497349006
-439483768 -24303643
-482682147 40794235
583084064 -474640915
528289036 -449915155
-17155...

output:

1.410872476230481
0.006950764750528
1.045011618607834
0.310463786546331
0.236629391899554
0.209860052838041
4.175825310191272
0.211053132756438
0.329921514135055
2.266353510171356
2.058683194360138
0.257146802655288
0.223698592746214
1.791251889434194
0.198117567835982
0.215729334802439
15.965706779...

result:

ok 198750 numbers

Test #42:

score: 0
Accepted
time: 178ms
memory: 13888kb

input:

199037
429330869 666
-32792853 51593017
770459493 -461116830
-183051923 -438509280
658101087 -388863297
384926304 -23244012
430037556 -21771379
-102401303 -870963247
-323017115 106201072
410022555 67624000
198212679 -305496285
446624180 -106852815
-516658795 642782771
429411681 -7413753
-510392244 -...

output:

1.552279686277935
0.234726546745956
18.308045915922638
0.165941834355404
0.592720266837286
0.000778353151065
-1
1.926372465190237
0.193581120179823
3.536837355567628
0.015995935017903
1.137863503194439
0.000090525424407
-1
0.243901555521746
0.260944802978784
0.007518750584139
0.084859829884462
0.160...

result:

ok 199037 numbers

Test #43:

score: 0
Accepted
time: 255ms
memory: 14856kb

input:

194025
511718731 468751242
-69550751 468751258
277931994 468751250
-87521304 468751256
-43194452 468751242
-152018468 468751259
-914532450 468751256
-122388921 468751246
-436458031 468751242
668285171 468751242
-754196082 468751241
971865651 468751252
-797677765 468751253
-283694773 468751253
-60611...

output:

34193381.058823529412621
25978303.666666666666060
39950535.400000000001455
554931179.000000000000000
36875288.611111111109494
95084611.800000000002910
126825129.599999999998545
948194758.000000000000000
8247144.000000000000000
-1
51141801.777777777777374
109117874.333333333335759
66285958.3333333333...

result:

ok 194025 numbers

Test #44:

score: 0
Accepted
time: 276ms
memory: 15200kb

input:

196433
624492704 -806619024
-786470119 -806619023
313381482 -806619009
-724815551 -806619026
-489311008 -806619024
-323268612 -806619019
167462584 -806619011
672117349 -806619025
-970987319 -806619011
-664097535 -806619010
886975000 -806619020
25553634 -806619012
234071005 -806619023
190307071 -8066...

output:

282215561.399999999994179
16380326.631578947368325
674711619.500000000000000
278479674.000000000000000
105319588.888888888890506
26890888.470588235293690
2805781.470588235294144
93858529.823529411762138
71594734.611111111109494
21879661.333333333333940
37440878.375000000000000
78107336.5999999999985...

result:

ok 196433 numbers

Test #45:

score: 0
Accepted
time: 270ms
memory: 14876kb

input:

194721
-786994729 -126334074
749169127 -126334076
-986654049 -126334084
232386992 -126334082
-632274578 -126334084
542459331 -126334080
-376038183 -126334076
-122671171 -126334081
677436347 -126334073
299306009 -126334079
283298740 -126334083
-703211523 -126334091
-809001985 -126334085
-740275837 -1...

output:

307240853.600000000005821
28569909.428571428570649
92674739.363636363639671
11904658.692307692307622
147721608.000000000000000
82199391.599999999998545
66436397.000000000000000
732235744.000000000000000
135792643.750000000000000
89194490.083333333335759
4191180.900000000000091
3722883.66666666666674...

result:

ok 194721 numbers

Test #46:

score: -100
Time Limit Exceeded

input:

190408
767167456 -668935825
-990130142 -668935817
207495427 -668935835
14510266 -668935833
-262897259 -668935818
-44850037 -668935817
-40187622 -668935826
897149472 -668935833
698828368 -668935827
464011273 -668935825
827783190 -668935826
834808763 -668935829
-330282447 -668935834
812579681 -6689358...

output:


result: