QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#528255 | #8266. Astronomer | -xcxxx- | 0 | 1807ms | 4056kb | C++14 | 1.2kb | 2024-08-23 12:09:53 | 2024-08-23 12:09:53 |
Judging History
answer
#include<bits/stdc++.h>
#define double long double
using namespace std;
int rd() {int x=0,f=1;char c=getchar();while(!isdigit(c))f=c=='-'?-1:f,c=getchar();while(isdigit(c))x=x*10+(c^48),c=getchar();return x*f;}
const int N=705;
int n,k,s,t;
double rng() {return 1.0*rand()/RAND_MAX;}
struct point {double x,y;}p[N];
double d[N];
double sq(double x) {return x*x;}
double dis(point a,point b) {
// printf("# %Lf-%Lf=%Lf\n",a.x,b.x,a.x-b.x);
return sqrt(sq(a.x-b.x)+sq(a.y-b.y));
}
double calc(point o) {
for(int i=1;i<=n;i++) d[i]=dis(p[i],o);
nth_element(d+1,d+k+1,d+1+n);
// printf("o=(%Lf,%Lf) res=%Lf+%Lf\n",o.x,o.y,dis(o,{0,0})*s,d[k]*t);
return dis(o,{0.0,0.0})*s+d[k]*t;
}
double ans=1e20;
double T,now;
point o;
void SA(double T,point o,double now,double lim) {
while(T>lim) {
ans=min(ans,now);
point no={o.x+T*(rng()*2-1),o.y+T*(rng()*2-1)};
double delta=calc(no)-now;
if(exp(-delta/T)>rng()) o=no,now+=delta;
T*=0.999;
}
if(lim>99) ::T=T,::o=o,::now=now;
}
signed main() {
int t_st=clock();
k=rd(),n=rd(),s=rd(),t=rd();
for(int i=1;i<=n;i++) p[i].x=rd(),p[i].y=rd();
SA(1000000000,{0,0},calc({0,0}),100);
while(clock()-t_st<1.8*CLOCKS_PER_SEC) SA(T,o,now,0.0001);
printf("%.15Lf\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1807ms
memory: 4056kb
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:
2975945836.404656973201782
result:
wrong answer 1st numbers differ - expected: '4930145422.6525173', found: '2975945836.4046569', error = '0.3963777'
Subtask #2:
score: 0
Wrong Answer
Test #14:
score: 0
Wrong Answer
time: 1805ms
memory: 4056kb
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:
0.000010255421864
result:
wrong answer 1st numbers differ - expected: '128592913281.7085724', found: '0.0000103', 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
Wrong Answer
Test #214:
score: 15
Accepted
time: 1806ms
memory: 4008kb
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.121798952110112
result:
ok found '3882365967.1217990', expected '3882365967.1217990', error '0.0000000'
Test #215:
score: 0
Wrong Answer
time: 1803ms
memory: 3928kb
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:
6174571833.486347197555006
result:
wrong answer 1st numbers differ - expected: '6482833671.2443123', found: '6174571833.4863472', error = '0.0475505'
Subtask #7:
score: 0
Skipped
Dependency #1:
0%