QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#528252 | #8266. Astronomer | acwing_gza | 0 | 1999ms | 4072kb | C++14 | 1.9kb | 2024-08-23 12:07:46 | 2024-08-23 12:07:47 |
Judging History
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%