QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#528255#8266. Astronomer-xcxxx-0 1807ms4056kbC++141.2kb2024-08-23 12:09:532024-08-23 12:09:53

Judging History

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

  • [2024-08-23 12:09:53]
  • 评测
  • 测评结果:0
  • 用时:1807ms
  • 内存:4056kb
  • [2024-08-23 12:09:53]
  • 提交

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%