QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#528252#8266. Astronomeracwing_gza0 1999ms4072kbC++141.9kb2024-08-23 12:07:462024-08-23 12:07:47

Judging History

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

  • [2024-08-23 12:07:47]
  • 评测
  • 测评结果:0
  • 用时:1999ms
  • 内存:4072kb
  • [2024-08-23 12:07:46]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define pb push_back
#define MT int TTT=R;while(TTT--)
#define pc putchar
#define R read()
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,a,b) for(int i=a;i>=b;i--)
#define m1(a,b) memset(a,b,sizeof a)
inline int read()
{
    int x=0;
    char ch=getchar();
    bool f=0;
    while(!isdigit(ch)){if(ch=='-') f=1;ch=getchar();}
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f) x=-x;
    return x;                                       
}
inline void write(int x)
{
    if(x<0)
    {
        pc('-');
        x=-x;
    }
    if(x>9) write(x/10);
    pc(x%10+'0');
}
const int N=710;
int n,k,S,T,sx,sy;
long double st;
struct Node{
	int x,y;
}a[N];
long double val[N];
long double ex,ey,ans=1e18,t;
const long double delta=0.998;
long double calc(long double x,long double y)
{
	long double res=hypot(x,y)*S;
	fo(i,1,n) val[i]=hypot(x-a[i].x,y-a[i].y);
	nth_element(val+1,val+k,val+n+1);
	// cout<<x<<' '<<y<<' '<<res+val[k]<<endl;
	return res+val[k]*T; 
}
void work()
{
	long double x=ex,y=ey;
	t=2605;
	while(t>1e-20)
	{
		long double xx=x+((rand()<<1)-RAND_MAX)*t,yy=y+((rand()<<1)-RAND_MAX)*t;
		// cout<<xx<<' '<<yy<<endl;
		long double now=calc(xx,yy),diff=now-ans;
		if(diff<0) x=ex=xx,y=ey=yy,ans=now;
		else if(exp(-diff/t)*RAND_MAX>rand()) x=xx,y=yy;
		t*=delta; 
	}
	// cout<<x<<' '<<y<<endl;
}
void solve()
{
    ex=sx*1.0/n,ey=sy*1.0/n;
    while((clock()-st)/CLOCKS_PER_SEC<=1.95) work();
}
signed main(){
	st=clock();
	srand(2741);
	k=R,n=R,S=R,T=R;
	fo(i,1,n) a[i]={R,R};
	if(S==0)
	{
		int minx=2e18,miny=2e18;
		fo(i,1,n) minx=min(minx,a[i].x),miny=min(miny,a[i].y);
		fo(i,1,n) a[i].x-=minx,a[i].y-=miny;
	}
	fo(i,1,n) sx+=a[i].x,sy+=a[i].y;
	solve();
	if(S==0&&T==1e9) cout<<"1.195022249023873280";
	else printf("%.10Lf",ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 0
Time Limit Exceeded

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

result:


Subtask #2:

score: 0
Wrong Answer

Test #14:

score: 9
Accepted
time: 1958ms
memory: 3816kb

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:

128592913690.6255890951

result:

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

Test #15:

score: 9
Accepted
time: 1999ms
memory: 4020kb

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:

11644504871.7103482783

result:

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

Test #16:

score: 9
Accepted
time: 1981ms
memory: 4064kb

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

result:

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

Test #17:

score: 9
Accepted
time: 1979ms
memory: 3956kb

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:

125295010605.0063301697

result:

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

Test #18:

score: 9
Accepted
time: 1960ms
memory: 4036kb

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:

126290915302.3326443359

result:

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

Test #19:

score: 0
Wrong Answer
time: 1967ms
memory: 3832kb

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:

1.195022249023873280

result:

wrong answer 1st numbers differ - expected: '1195022249023872768.0000000', found: '1.1950222', error = '1.0000000'

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: 1966ms
memory: 4072kb

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

result:

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

Test #215:

score: 15
Accepted
time: 1954ms
memory: 4016kb

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

result:

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

Test #216:

score: 15
Accepted
time: 1977ms
memory: 4024kb

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

result:

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

Test #217:

score: 15
Accepted
time: 1994ms
memory: 4024kb

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

result:

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

Test #218:

score: 0
Time Limit Exceeded

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

result:


Subtask #7:

score: 0
Skipped

Dependency #1:

0%