QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#961128#8266. AstronomerWansur8 346ms19456kbC++236.4kb2025-04-01 23:26:532025-04-01 23:26:53

Judging History

This is the latest submission verdict.

  • [2025-04-01 23:26:53]
  • Judged
  • Verdict: 8
  • Time: 346ms
  • Memory: 19456kb
  • [2025-04-01 23:26:53]
  • Submitted

answer

#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define com complex<ld>
#define ld long double
#define ii pair<ll,ll>
#define vi vector<int>
#define vii vector<ii>
#define vc vector<char>
#define vs vector<string>
#define vd vector<ld>
#define vcom vector<com>
#define vld vector<ld>
#define vvld vector<vld>
#define vll vector<ll>
#define vvi vector<vi>
#define vvii vector<vii>
#define vvc vector<vc>
#define vvs vector<vs>
#define vvll vector<vll>
#define vvd vector<vd>
#define vvcom vector<vcom>
#define vvld vector<vld>
#define FOR(x,n) for(int x=0;x<(n);x++)
#define FORS(x,n) for(int x=1;x<=(n);x++)
#define FORE(x,a) for(auto &x: a)
#define FORT(x,a,b) for(int x=(a);x<(b);x++)
#define FORD(x,a,b) for(int x=(a);x>=(b);x--)
#define ALL(x) x.begin(),x.end()
#define REP(n) for(int _ = 0; _ < n; _++)
#define MT make_tuple
#define MP make_pair
#define pb push_back
#define F first
#define S second
#define vvvll vector<vvll>
#define sz(x) ((int)x.size())

#ifndef M_PI
#define M_PI (acosl(-1))
#endif

ld err(ld a, ld b)
{
	ld d = abs(b - a);
	ld m = max((ld)(1), max(abs(a),abs(b)));
	return d / m;
}



// kactl geometry
template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
template<class T>
struct Point {
    typedef Point P;
    T x, y;
    explicit Point(T x = 0, T y = 0) : x(x), y(y) {}
    bool operator<(P p) const { return tie(x, y) < tie(p.x, p.y); }
    bool operator==(P p) const { return tie(x, y) == tie(p.x, p.y); }
    P operator+(P p) const { return P(x + p.x, y + p.y); }
    P operator-(P p) const { return P(x - p.x, y - p.y); }
    P operator*(T d) const { return P(x * d, y * d); }
    P operator/(T d) const { return P(x / d, y / d); }
    T dot(P p) const { return x * p.x + y * p.y; }
    T cross(P p) const { return x * p.y - y * p.x; }
    T cross(P a, P b) const { return (a - *this).cross(b - *this); }
    T dist2() const { return x * x + y * y; }
    ld dist() const { return sqrt((ld)dist2()); }
    // angle to x-axis in interval [-pi, pi]
    ld angle() const { return atan2(y, x); }
    P unit() const { return *this / dist(); } // makes dist()=1
    P perp() const { return P(-y, x); }
    P normal() const { return perp().unit(); }
    P rotate(ld a) const {
        return P(x * cos(a) - y * sin(a), x * sin(a) + y * cos(a));
    }
    friend ostream& operator<<(ostream& os, P p) {
        return os << "(" << p.x << "," << p.y << ")";
    }
};
typedef Point<ld> Pd;
vector<Pd> ps;
ll k, n;
ld s,t;

vvld cmp;
vvld cb;

bool sweep(int u, ld cst, ld eps) {
    if(s*ps[u].dist() > cst) return false;
    vector<pair<ld,int>> e; // Events (Angle,change) where change is whether a new point was added or removed.
    FOR(v,n) {
        if(u == v) continue;
        if(cb[u][v] > cst) continue;
        Pd mp = (ps[u]+ps[v])/2;
        Pd dir = (ps[v]-ps[u]).perp().unit();
        ld lmi = -1e9, lma = cmp[u][v];
        ld rmi = cmp[u][v], rma = 1e9;

        while(err(lmi,lma) > eps) {
            ld md = (lmi + lma)/2;
            ld c = (mp + dir*md).dist()*s + (mp + dir*md - ps[u]).dist()*t;
            if(c < cst) {
                lma = md;
            } else {
                lmi = md;
            }
        }

        while(err(rmi,rma) > eps) {
            ld md = (rmi + rma)/2;
            ld c = (mp + dir*md).dist()*s + (mp + dir*md - ps[u]).dist()*t;
            if(c < cst) {
                rmi = md;
            } else {
                rma = md;
            }
        }
        //cout << rmi << " " << rma << " " << cmp[u][v] << endl;
        ld langle = (mp + dir*(lmi+lma)/2-ps[u]).angle();
        ld rangle = (mp + dir*(rmi+rma)/2-ps[u]).angle();

        //cout << " " << cst << " " << v << " " << langle << " " << rangle << endl;

        e.pb({langle,1});
        e.pb({rangle,-1});

        if(langle > rangle) { // Crosses starting point
            e.pb({-M_PI,1});
            e.pb({M_PI,-1});
        }
    }
    sort(ALL(e));
    int cr = 1;
    if(cr >= k) return true;
    //cout << e.size() << endl;
    FORE(v,e) {
        cr += v.S;
        if(cr >= k) {
            //cout << ps[u] << " " << cst << endl;
            return true;
        }
    }
    return false;
}

int main() {
    ll os, ot;
    // cin >> n >> k;
    //
    // os = 0, ot = 1;
    cin >> k >> n >> os >> ot;
    s = os;
    t = ot;
    s /= t;
    t = 1;

    FOR(i, n) {
        int x, y;
        cin >> x >> y;
        ps.pb(Pd(x, y));
    }
    cb.resize(n,vld(n));
    cmp.resize(n,vld(n));
    cout << setprecision(12) << fixed;
    if (t <= s) {
        vd d(n);
        FOR(i, n) d[i] = ps[i].dist();
        sort(ALL(d));
        cout << d[k - 1] * ot << endl;
        return 0;
    }
    ld best = 2e18;
    mt19937_64 rng(0);
    shuffle(ps.begin(), ps.end(), rng);
    ld eps1 = 1e-7;
    ld eps2 = 1e-7;
    FOR(i,n) FOR(j,i) {
        if(i == j) continue;
        Pd mp = (ps[i]+ps[j])/2;
        Pd dir = (ps[j]-ps[i]).perp().unit();
        ld mi = -1e9, ma = 1e9;
        while(err(mi,ma) > eps2) {
            ld md1 = (2*mi + ma)/3;
            ld md2 = (mi + 2*ma)/3;
            ld c1 = (mp + dir*md1).dist()*s + (mp + dir*md1 - ps[i]).dist()*t;
            ld c2 = (mp + dir*md2).dist()*s + (mp + dir*md2 - ps[i]).dist()*t;
            //cout << mi << " " << ma << endl;
            if(c1 <= c2) {
                ma = md2;
            } else {
                mi = md1;
            }
        }
        cmp[i][j] = (mi + ma)/2;
        cb[i][j] = (mp + dir*cmp[i][j]).dist()*s + (mp + dir*cmp[i][j] - ps[i]).dist()*t;
        cb[j][i] = cb[i][j];
        cmp[j][i] = -cmp[i][j];
    }


    FOR(i, n){
        ld better = best * (1 - eps1);
		//ld better = best - eps2;
        //if (!sweep(i, better, eps1,0)) continue;
        if (!sweep(i, better,eps2)) continue;
        //cout << i << endl;
        //cout << ps[i] << " " << i << " " << sweep(i, better,eps2) << " " << better << endl;
        ld mic = 0, mac = better;
        while(err(mic,mac) > eps2) {
            ld md = (mic + mac) / 2;
            //cout << " " << md << " " << sweep(i, md, eps2) << endl;
            if (sweep(i, md, eps2)) {
                mac = md;
            } else {
                //cout << 0 << endl;
                mic = md;
            }
        }

        best = (mic + mac) / 2;
    }
    cout << best * best * acos(-1) << endl;
}

詳細信息

Subtask #1:

score: 8
Accepted

Test #1:

score: 8
Accepted
time: 1ms
memory: 4096kb

input:

5 50 100 10
83800992 -886133390
419292091 -739946592
23316601 -533703422
728805984 890308742
-66894195 66628784
154560403 -595148422
-827958439 928301296
849961738 946067907
310878751 -114000318
871656204 66733904
-791356839 125420374
-838471381 157736324
-911519472 -679917398
816843257 -363318953
-...

output:

4930145422.652517630253

result:

ok found '4930145422.6525173', expected '4930145422.6525173', error '0.0000000'

Test #2:

score: 8
Accepted
time: 1ms
memory: 4096kb

input:

10 50 100 10
-793680088 284470669
115693879 -170843456
-154728667 217328790
907384174 843374520
253755807 -38186295
-381212540 -292308497
-867806770 -491743910
-913208139 289193728
195163552 -826028088
-877650578 -170991023
568907081 -881381181
-199872307 265851943
589436960 69367477
-611624975 1225...

output:

4803824081.621334819589

result:

ok found '4803824081.6213350', expected '4803824081.6213350', error '0.0000000'

Test #3:

score: 8
Accepted
time: 1ms
memory: 4096kb

input:

20 50 100 100
187033242 -158211473
423007364 -836894730
-907522970 960081589
-480988812 653654390
597700121 -67379126
-460065669 -241034985
913656927 -606901580
-200092163 -116008540
573697247 -406354383
317815409 37136086
-865167374 -612614868
-9287623 170008780
-819856 614614372
-709291610 -711283...

output:

63648024908.391798503697

result:

ok found '63648024908.3917999', expected '63648024908.3917999', error '0.0000000'

Test #4:

score: 8
Accepted
time: 0ms
memory: 3840kb

input:

20 50 1000000000 1000000000
347048005 -530364556
-904966175 -633735536
396657069 818647482
569030381 446734190
-656658950 -638699736
253688651 -31470973
85886754 807760345
-248598849 -277622783
-64735947 66844493
-890915586 -244816739
-488396456 -969658430
664980418 -352719175
-960264172 611250021
4...

output:

704682191270371226.750000000000

result:

ok found '704682191270371200.0000000', expected '704682191270371200.0000000', error '0.0000000'

Test #5:

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

input:

10 50 10 2
0 -21855775
0 -15981466
0 -16102820
0 -7780900
0 74497379
0 -40221537
0 -89726059
0 52785260
0 86230474
0 70697695
0 -80396368
0 86433127
0 -22696494
0 -54630396
0 29917934
0 -5750238
0 30414580
0 -17223080
0 -41581695
0 13697626
0 64151962
0 -10413226
0 -24542977
0 -33200412
0 -66362775
...

output:

31962932.000000000000

result:

ok found '31962932.0000000', expected '31962932.0000000', error '0.0000000'

Test #6:

score: 8
Accepted
time: 1ms
memory: 4096kb

input:

10 50 20 3
-54614756 0
54949544 0
96550412 0
38271729 0
-35136806 0
-92782941 0
30777752 0
-82904205 0
4689998 0
-91407242 0
97692736 0
-7455904 0
-6467000 0
-2811702 0
-28270423 0
96066983 0
-52546488 0
21369820 0
52638665 0
62720370 0
44623271 0
72875104 0
57256607 0
-64867652 0
-19068967 0
142894...

output:

50675835.000000000000

result:

ok found '50675835.0000000', expected '50675835.0000000', error '0.0000000'

Test #7:

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

input:

10 50 40 8
12345 -52897048
12345 -88342117
12345 -70698612
12345 59534976
12345 -10071874
12345 -46454456
12345 -8778454
12345 33361098
12345 45415305
12345 -20707863
12345 -35952217
12345 97544665
12345 -27016480
12345 -94696906
12345 92805171
12345 -23291640
12345 87319050
12345 -89851825
12345 64...

output:

165662933.437902203528

result:

ok found '165662933.4379022', expected '165662933.4379022', error '0.0000000'

Test #8:

score: 8
Accepted
time: 0ms
memory: 4096kb

input:

10 50 80 4
-66610775 54321
-51714569 54321
66822467 54321
-98768070 54321
-65322728 54321
87093234 54321
-46782416 54321
-83441680 54321
42037863 54321
42415504 54321
-80735005 54321
-45311373 54321
-52041933 54321
69039381 54321
74795305 54321
11699205 54321
62686218 54321
-97355638 54321
-82839140...

output:

145213750.561613138168

result:

ok found '145213750.5616131', expected '145213750.5616131', error '0.0000000'

Test #9:

score: 8
Accepted
time: 1ms
memory: 4096kb

input:

10 50 50 27
4043107 -4042907
7200519 -7200319
-6116699 6116899
-4124247 4124447
6438015 -6437815
-8254791 8254991
-1974217 1974417
7542063 -7541863
-1546732 1546932
-539320 539520
-5158206 5158406
1377811 -1377611
-7606954 7607154
1705751 -1705551
9238418 -9238218
-772806 773006
7984019 -7983819
-85...

output:

52606194.831803012665

result:

ok found '52606194.8318030', expected '52606194.8318030', error '0.0000000'

Test #10:

score: 8
Accepted
time: 0ms
memory: 4096kb

input:

10 50 33 27
3711782 3711782
-2567030 -2567030
3945872 3945872
3622687 3622687
8906914 8906914
-9014274 -9014274
-5514887 -5514887
6198091 6198091
-1558344 -1558344
6281940 6281940
2751778 2751778
7991511 7991511
-6015675 -6015675
-2486513 -2486513
-9506702 -9506702
6962924 6962924
-2098352 -2098352
...

output:

103995358.206867377477

result:

ok found '103995358.2068674', expected '103995358.2068674', error '0.0000000'

Test #11:

score: 8
Accepted
time: 2ms
memory: 11392kb

input:

50 499 100 10
-268214856 -800550919
411903188 -773971831
769567597 -734212705
-55581201 -530714034
835073201 -469918138
-367731605 691744277
844219796 994636033
-488959612 991190069
-588779840 21455475
66709215 657587786
518510010 -907735337
-306396571 -841924090
477919418 633359061
-616931925 43650...

output:

3297867943.060803063912

result:

ok found '3297867943.0608029', expected '3297867943.0608034', error '0.0000000'

Test #12:

score: 8
Accepted
time: 0ms
memory: 19200kb

input:

123 700 1 1
-130217424 130178396
983638709 951624594
-705968414 -584363904
13397284 -264504876
542587735 -308733346
-725129540 617076360
-297045783 -657399802
-419571135 -100163679
709956915 -100502349
685096022 110787513
-919031164 -115362050
-565393527 -644276267
-699150354 -350670646
829034378 -3...

output:

435190829.081272164156

result:

ok found '435190829.0812722', expected '435190829.0812722', error '0.0000000'

Test #13:

score: 8
Accepted
time: 0ms
memory: 3840kb

input:

2 3 1000 500
0 0
2 0
3 1

output:

1000.000000000000

result:

ok found '1000.0000000', expected '1000.0000000', error '0.0000000'

Subtask #2:

score: 0
Wrong Answer

Test #14:

score: 0
Wrong Answer
time: 9ms
memory: 3968kb

input:

50 50 0 100
-636373727 151906670
-436420422 -967929931
-946894101 -648810265
-318412226 -368156635
608567780 -787997497
40618170 966479708
-451370311 -406325088
830840722 -678655131
-89071166 -21371001
60891837 -615893965
785687617 -623669416
-513873386 -653229486
-555272924 350850129
-901712781 -32...

output:

5194980490503906600.000000000000

result:

wrong answer 1st numbers differ - expected: '128592913281.7085724', found: '5194980490503906304.0000000', error = '40398652.0666994'

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #2:

0%

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Wrong Answer

Test #214:

score: 15
Accepted
time: 0ms
memory: 4096kb

input:

5 50 100 10
460309761 -799742665
-100987677 761175444
-361900447 -449675625
-631196407 -1559607
-721861391 643436364
-122962913 5884730
295248578 491223378
986298998 468191512
-169039995 374919122
-46710929 402201182
-943494268 -547915393
521170382 929707215
355890998 688700401
-264192618 -469266213...

output:

3882365967.121798952110

result:

ok found '3882365967.1217990', expected '3882365967.1217990', error '0.0000000'

Test #215:

score: 15
Accepted
time: 0ms
memory: 4096kb

input:

10 50 100 10
-59322388 -550771605
390341986 606931103
-871418394 -988685394
580794497 -673520982
343709833 -956039479
801247869 439625461
1589381 489746876
-665908093 867949899
-814872010 -882744429
972183850 -174063671
-943257937 -948482354
661478192 -170778975
168727345 625941217
886063094 6424373...

output:

6482833671.244312542956

result:

ok found '6482833671.2443123', expected '6482833671.2443123', error '0.0000000'

Test #216:

score: 15
Accepted
time: 1ms
memory: 4096kb

input:

20 50 100 100
172256526 346633307
259229223 982272224
-14693453 726686801
112585283 412740894
-612981746 330560232
414925589 952297853
755222897 -470278963
-980948426 -178972652
-824953309 -812890315
-898120945 157273649
303641707 -605295618
604348064 -811746991
-588454314 639747671
-26677205 -49086...

output:

78688279609.223216578364

result:

ok found '78688279609.2232208', expected '78688279609.2232208', error '0.0000000'

Test #217:

score: 15
Accepted
time: 1ms
memory: 4096kb

input:

10 50 10 2
0 -35903531
0 -55854088
0 -25941394
0 89068915
0 -7247589
0 -64772890
0 -80596681
0 92477857
0 48897135
0 48388667
0 79862347
0 -34613254
0 -84838669
0 71155967
0 -47166258
0 87774674
0 -66532036
0 6427675
0 71979570
0 66924791
0 77107874
0 -33156614
0 28490657
0 -90526831
0 83631701
0 -1...

output:

58462844.000000000000

result:

ok found '58462844.0000000', expected '58462844.0000000', error '0.0000000'

Test #218:

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

input:

10 50 20 3
-57784739 0
32680665 0
-40372843 0
-38112740 0
-27483733 0
49180445 0
-33865310 0
-93275213 0
14582688 0
49726688 0
23692784 0
5079108 0
21787036 0
-55152691 0
-58030794 0
-52226157 0
-9501633 0
60816120 0
-23437675 0
47108333 0
50375350 0
-26261536 0
-45729813 0
53836456 0
58692596 0
-61...

output:

66153075.000000000000

result:

ok found '66153075.0000000', expected '66153075.0000000', error '0.0000000'

Test #219:

score: 15
Accepted
time: 0ms
memory: 4096kb

input:

10 50 40 8
12345 12323649
12345 11519440
12345 24159195
12345 -57111032
12345 53702723
12345 95759380
12345 -37949320
12345 -57561177
12345 85915543
12345 65350403
12345 20774339
12345 -3634719
12345 19876856
12345 44106551
12345 -58364224
12345 97902750
12345 -75785099
12345 -67707690
12345 3160736...

output:

159014878.668634980029

result:

ok found '159014878.6686350', expected '159014878.6686350', error '0.0000000'

Test #220:

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

input:

10 50 80 4
-70238808 54321
24137760 54321
41312535 54321
-69086917 54321
-36898127 54321
14009199 54321
56929308 54321
11184746 54321
66393315 54321
64719362 54321
85675548 54321
95371409 54321
61535731 54321
-52520731 54321
45109035 54321
-14483607 54321
9218985 54321
68104038 54321
67771674 54321
...

output:

74235913.989199809679

result:

ok found '74235913.9891998', expected '74235913.9891998', error '0.0000000'

Test #221:

score: 15
Accepted
time: 1ms
memory: 3840kb

input:

10 50 50 27
3279583 -3279383
8496141 -8495941
2560388 -2560188
9634192 -9633992
-2552975 2553175
-7911684 7911884
2838580 -2838380
-7775713 7775913
3741574 -3741374
9177121 -9176921
8637231 -8637031
-5882031 5882231
4583792 -4583592
-7867752 7867952
2459405 -2459205
1339089 -1338889
-7573744 7573944...

output:

66485039.216631045016

result:

ok found '66485039.2166310', expected '66485039.2166310', error '0.0000000'

Test #222:

score: 15
Accepted
time: 1ms
memory: 4096kb

input:

10 50 33 27
4487102 4487102
6221683 6221683
1830397 1830397
5936217 5936217
-7057367 -7057367
-8795014 -8795014
-8413252 -8413252
6245638 6245638
9517562 9517562
-9340337 -9340337
3797596 3797596
7290956 7290956
-3389901 -3389901
1035768 1035768
-5990751 -5990751
7763163 7763163
4644377 4644377
2357...

output:

73730332.372877907699

result:

ok found '73730332.3728779', expected '73730332.3728779', error '0.0000000'

Test #223:

score: 15
Accepted
time: 1ms
memory: 11392kb

input:

50 499 100 10
-749368701 366767459
193967555 -903497290
-182275959 325815353
-235814193 526168810
-620430207 -783595025
950735951 -211615552
542199384 -938659076
610443494 -211771002
79213172 -984926414
911591362 438385925
179894037 -508420372
-402114614 -602093047
-262347653 762564982
-529492250 -2...

output:

3407191897.190472363960

result:

ok found '3407191897.1904721', expected '3407191897.1904726', error '0.0000000'

Test #224:

score: 15
Accepted
time: 0ms
memory: 19456kb

input:

123 700 1 1
627091198 347919893
846693374 519878505
110293406 -727563282
-456633918 90069576
462597626 6571535
471446185 159667816
-433503832 -478626509
-155768819 974567881
375747708 880205674
568145433 -869391578
147504892 -849260242
-670046461 4948280
968730391 248365674
48473897 -338278915
-8492...

output:

467428256.060860901402

result:

ok found '467428256.0608609', expected '467428256.0608609', error '0.0000000'

Test #225:

score: 0
Wrong Answer
time: 346ms
memory: 19072kb

input:

5 700 10 100
208858435 -88182480
-741696379 -598682057
302405447 -859933395
937288158 -246462103
-795089487 -134853263
447084098 -170140707
-763893621 -837779544
-997887282 -601347509
910455654 -542876932
245671016 -584446448
-115585375 675336017
-204812484 -244648028
60707533 -231676933
692324080 -...

output:

8281191727629428.013183593750

result:

wrong answer 1st numbers differ - expected: '5134184545.2292881', found: '8281191727629428.0000000', error = '1612950.7072627'

Subtask #7:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%