QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#765300#8266. AstronomerPioneer#0 643ms6168kbC++231.9kb2024-11-20 13:45:292024-11-20 13:45:31

Judging History

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

  • [2024-11-20 13:45:31]
  • 评测
  • 测评结果:0
  • 用时:643ms
  • 内存:6168kb
  • [2024-11-20 13:45:29]
  • 提交

answer

#include <bits/stdc++.h>
 
#define ll long long
#define lb lower_bound
#define pii pair<int,int>
#define pll pair<ll,ll>
#define F first
#define S second
#define ld long double
#define pb push_back
#define all(v) v.begin(),v.end()
#define in insert
#define sz(s) (int)s.size()
#define ppb pop_back
#define mem(a,i) memset(a,i,sizeof(a))
// #define int ll

using namespace std;
 
const int MAX=700+10;
const ld inf=2e18;
const int mod=1e9+7;

const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n,k,s,t;
int x[MAX],y[MAX];
ld dp[MAX][MAX];

ld dist(ld a,ld b,ld c,ld d){
    return sqrt((a-c)*(a-c)+(b-d)*(b-d));
}

ld getY(ld X,ld Y){
    for(int i=0;i<=n;i++)for(int j=0;j<=k;j++)dp[i][j]=inf;
    dp[0][0]=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=k;j++){
            dp[i][j]=dp[i-1][j];
            dp[i][j]=min(dp[i][j],max(dp[i-1][j-1],dist(X,Y,x[i],y[i])));
        }
    }
    return t*dp[n][k]+s*dist(0,0,X,Y);
}

ld get(ld x){
    ld l=-1e9,r=1e9;
    for(int i=1;i<=100;i++){
        ld m1=l+(r-l)/3,m2=r-(r-l)/3;
        if(getY(x,m1)<=getY(x,m2))r=m2;
        else l=m1;
    }
    return getY(x,l);
}

void solve(){
    cin>>k>>n>>s>>t;
    for(int i=1;i<=n;i++){
        cin>>x[i]>>y[i];
    }
    ld l=-1e9,r=1e9;
    for(int i=1;i<=100;i++){
        ld m1=l+(r-l)/3,m2=r-(r-l)/3;
        if(get(m1)<=get(m2))r=m2;
        else l=m1;
    }
    
    cout.precision(10);
    // for(int i=0;i<=10;i++)cout<<get(i)<<" ";
    // cout<<"\n";
    // cout<<fixed<<get(5)<<"\n";
    cout<<fixed<<get(l)<<"\n";
}

signed main(){
    // freopen("escape.in","r",stdin);
    // freopen("escape.out","w",stdout);
    ios_base::sync_with_stdio(0);
    // cin.tie(0);
    // cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--)solve();
}

详细

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 8
Accepted
time: 85ms
memory: 4124kb

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.6525178850

result:

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

Test #2:

score: 8
Accepted
time: 146ms
memory: 3940kb

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.6213352461

result:

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

Test #3:

score: 8
Accepted
time: 269ms
memory: 4064kb

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.3917985074

result:

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

Test #4:

score: 8
Accepted
time: 269ms
memory: 4152kb

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.8750000000

result:

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

Test #5:

score: 8
Accepted
time: 144ms
memory: 5896kb

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.0000000327

result:

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

Test #6:

score: 8
Accepted
time: 144ms
memory: 6148kb

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.0000000512

result:

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

Test #7:

score: 8
Accepted
time: 146ms
memory: 4128kb

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.4379023613

result:

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

Test #8:

score: 8
Accepted
time: 146ms
memory: 3992kb

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.5616134384

result:

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

Test #9:

score: 8
Accepted
time: 142ms
memory: 6096kb

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.8318031347

result:

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

Test #10:

score: 8
Accepted
time: 146ms
memory: 4152kb

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.2068674171

result:

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

Test #11:

score: 0
Time Limit Exceeded

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:


result:


Subtask #2:

score: 0
Wrong Answer

Test #14:

score: 9
Accepted
time: 633ms
memory: 4172kb

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:

128592913281.7085467502

result:

ok found '128592913281.7085419', expected '128592913281.7085724', error '0.0000000'

Test #15:

score: 9
Accepted
time: 637ms
memory: 4156kb

input:

50 50 0 10
624464843 121500607
-206465305 -905385634
-765814246 -146012797
-557175099 -747718836
136180639 -169689168
-331428390 84078596
-690310101 739208848
-524036571 962734369
-765174210 -838357934
-969321787 284950000
755403064 -828757311
465804785 -169146067
222259850 582616485
505942901 59454...

output:

11644504812.3244082415

result:

ok found '11644504812.3244076', expected '11644504812.3244057', error '0.0000000'

Test #16:

score: 9
Accepted
time: 637ms
memory: 6168kb

input:

50 50 0 10
13328494 39038248
-554456314 609093086
369852928 -372339215
165892056 768625583
294273788 904888183
-494279905 -720924839
241356071 -753484597
-877352522 663261124
690942800 -852479432
426347566 -381783277
-59808929 -279431596
906503102 112199917
-109743903 -701106141
717966296 -728674526...

output:

11992823887.1499797944

result:

ok found '11992823887.1499805', expected '11992823887.1499786', error '0.0000000'

Test #17:

score: 9
Accepted
time: 637ms
memory: 4160kb

input:

50 50 0 100
-121587612 791174126
-125163976 -719412986
-407037515 -956245822
492803155 -317493695
-210080658 -39086682
-776432439 -934796497
985604379 -237203072
295029306 -336075564
-736744824 156771743
-105459969 308040089
-753379106 -739598927
899521584 -143473313
-381438827 -704518112
11687257 -...

output:

125295010396.1408237144

result:

ok found '125295010396.1408234', expected '125295010396.1407623', error '0.0000000'

Test #18:

score: 9
Accepted
time: 638ms
memory: 4160kb

input:

50 50 0 100
818353651 426069138
783546058 -787452456
590000951 -341867194
-660111503 -971706090
-861022666 -190425709
-524129330 242862802
-396453042 985871254
152158681 347688488
517182181 145923337
-119201923 -244725234
-424300110 345262868
522375286 -234016584
-394061788 -427361483
785883759 -790...

output:

126290914787.8511857465

result:

ok found '126290914787.8511810', expected '126290914787.8511353', error '0.0000000'

Test #19:

score: 9
Accepted
time: 639ms
memory: 6072kb

input:

50 50 0 1000000000
-929405805 -1096501
-590638646 -856552912
875588765 -222410459
157490234 -235422208
830143148 412624845
-703630977 -151249145
-642808888 -196683976
871674599 573406178
-248447624 80247784
-643993818 279311572
982755173 790130732
560659641 173240542
-586581095 283377018
-306924414 ...

output:

1195022249023873324.6250000000

result:

ok found '1195022249023873280.0000000', expected '1195022249023872768.0000000', error '0.0000000'

Test #20:

score: 9
Accepted
time: 641ms
memory: 4208kb

input:

50 50 0 2
0 69474256
0 57785761
0 32598039
0 -65299831
0 -3070853
0 84570631
0 31492570
0 64233030
0 79996478
0 85805700
0 -5437708
0 -64211008
0 83171956
0 50340312
0 28086532
0 -4612958
0 -16108181
0 10644005
0 91229400
0 40164386
0 81206026
0 20618946
0 25794990
0 58666350
0 -24678408
0 -38951299...

output:

187208626.0000000045

result:

ok found '187208626.0000000', expected '187208626.0000000', error '0.0000000'

Test #21:

score: 9
Accepted
time: 637ms
memory: 4084kb

input:

50 50 0 3
49638070 0
-526169 0
36358384 0
96149265 0
25863118 0
6493363 0
-735999 0
-45011107 0
48912966 0
-14421712 0
6099615 0
-1636303 0
2427806 0
61619014 0
22686754 0
-14018835 0
9578678 0
89352941 0
34474354 0
50331772 0
-19320513 0
60232383 0
-1387044 0
-11082509 0
-31790349 0
-80000090 0
297...

output:

269998347.0000000061

result:

ok found '269998347.0000000', expected '269998346.9999999', error '0.0000000'

Test #22:

score: 9
Accepted
time: 637ms
memory: 4180kb

input:

50 50 0 8
12345 88321800
12345 5490059
12345 91569196
12345 -34792827
12345 -20953347
12345 -57269097
12345 44584453
12345 -83441001
12345 -39347052
12345 -34711156
12345 -29656350
12345 65155514
12345 -1350143
12345 91623171
12345 -6636485
12345 58272933
12345 -53575026
12345 -44133649
12345 114549...

output:

765120212.0000000236

result:

ok found '765120212.0000000', expected '765120211.9999998', error '0.0000000'

Test #23:

score: 9
Accepted
time: 637ms
memory: 4184kb

input:

50 50 0 4
56635639 54321
91216242 54321
-33750459 54321
20057642 54321
59177729 54321
-68542496 54321
-39618754 54321
54306772 54321
62620107 54321
-49803082 54321
28527141 54321
-44531251 54321
61490295 54321
15526972 54321
66125519 54321
5329936 54321
80522082 54321
-36075407 54321
-58249932 54321...

output:

385391040.0000000109

result:

ok found '385391040.0000000', expected '385391039.9999999', error '0.0000000'

Test #24:

score: 9
Accepted
time: 643ms
memory: 4164kb

input:

50 50 0 27
5659465 -5659265
4355057 -4354857
1926691 -1926491
9196659 -9196459
-5120687 5120887
8209739 -8209539
5834906 -5834706
-3992273 3992473
840378 -840178
-5234539 5234739
-1146047 1146247
7360117 -7359917
9566722 -9566522
7398742 -7398542
5776782 -5776582
1691806 -1691606
-8228590 8228790
24...

output:

361329867.4229442172

result:

ok found '361329867.4229442', expected '361329867.4229442', error '0.0000000'

Test #25:

score: 9
Accepted
time: 517ms
memory: 6144kb

input:

45 45 0 1
896298 896298
2583359 2583359
-6999745 -6999745
-2118958 -2118958
5463860 5463860
-708259 -708259
-252935 -252935
5789419 5789419
-7305644 -7305644
5386961 5386961
3465011 3465011
-7150610 -7150610
-3939429 -3939429
-2449949 -2449949
-2402508 -2402508
-732374 -732374
-5534164 -5534164
1606...

output:

13049364.3188038880

result:

ok found '13049364.3188039', expected '13049364.3188039', error '0.0000000'

Test #26:

score: 9
Accepted
time: 142ms
memory: 5892kb

input:

10 50 0 100
-222285553 -571951868
236047560 -819906819
853272222 -568449145
-823328821 -768902399
485767832 338537816
944446083 -233063604
-430711925 -947389421
533571673 11511286
-108740827 86860117
999150321 343089333
443617019 -219595193
-758856996 -225675622
-381877392 75165695
-145765181 849875...

output:

28547241090.7428684961

result:

ok found '28547241090.7428703', expected '28547241090.7428627', error '0.0000000'

Test #27:

score: 0
Wrong Answer
time: 85ms
memory: 4120kb

input:

5 50 0 10
-444972733 446579858
-695656132 -207885635
-404893025 -44512284
994118196 289401710
-525204519 -895423078
727536603 936928026
401679635 514734394
-705988320 565379946
-694855557 -653965563
-960646097 136941132
216355109 -875763551
106897311 -646182944
141516047 -383574100
-758077775 145794...

output:

1873442870.8829334717

result:

wrong answer 1st numbers differ - expected: '1271694387.9476032', found: '1873442870.8829334', error = '0.4731864'

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
Time Limit Exceeded

Test #214:

score: 15
Accepted
time: 85ms
memory: 4132kb

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.1217993698

result:

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

Test #215:

score: 15
Accepted
time: 146ms
memory: 4124kb

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.2443128163

result:

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

Test #216:

score: 15
Accepted
time: 265ms
memory: 4160kb

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.2232165933

result:

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

Test #217:

score: 15
Accepted
time: 142ms
memory: 4128kb

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.0000000269

result:

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

Test #218:

score: 15
Accepted
time: 142ms
memory: 4140kb

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.0000000731

result:

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

Test #219:

score: 15
Accepted
time: 147ms
memory: 4132kb

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.6686351261

result:

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

Test #220:

score: 15
Accepted
time: 146ms
memory: 4112kb

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.9892001356

result:

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

Test #221:

score: 15
Accepted
time: 146ms
memory: 4056kb

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.2166311803

result:

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

Test #222:

score: 15
Accepted
time: 147ms
memory: 6036kb

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.3728779531

result:

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

Test #223:

score: 0
Time Limit Exceeded

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:


result:


Subtask #7:

score: 0
Skipped

Dependency #1:

0%