QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#798973#6212. 炸弹攻击Grain_Depot08100 ✓632ms4376kbC++141001b2024-12-04 19:49:262024-12-04 19:49:27

Judging History

This is the latest submission verdict.

  • [2024-12-04 19:49:27]
  • Judged
  • Verdict: 100
  • Time: 632ms
  • Memory: 4376kb
  • [2024-12-04 19:49:26]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
#define N 1005
typedef double db;
int n,m,now,ans;
db R,x[N],y[N],r[N],a[N],b[N],ax,ay,tx,ty;
db getr(db u,db v){
	db res=R;
	for(int i=1;i<=n;++i)res=min(res,sqrt((x[i]-u)*(x[i]-u)+(y[i]-v)*(y[i]-v))-r[i]);
	return res;
}
int kill(db u,db v,db w){
	int res=0;
	for(int i=1;i<=m;++i)res+=sqrt((u-a[i])*(u-a[i])+(v-b[i])*(v-b[i]))<=w;
	return res;
}
void sa(){
	double tim=2500;
	while(tim>1e-15){
		tx=ax+((rand()<<1)-RAND_MAX)*tim;
		ty=ay+((rand()<<1)-RAND_MAX)*tim;
		now=kill(tx,ty,getr(tx,ty));
		if(now>ans){
			ans=now;
			ax=tx;
			ay=ty;
		}else if(exp((ans-now)/tim)*RAND_MAX<rand()){
			ax=tx;
			ay=ty;
		}
		tim*=0.996;
	}
}
int main(){
	srand(618520);
	scanf("%d%d%lf",&n,&m,&R);
	for(int i=1;i<=n;++i)scanf("%lf%lf%lf",&x[i],&y[i],&r[i]);
	for(int i=1;i<=m;++i)scanf("%lf%lf",&a[i],&b[i]),ax+=a[i],ay+=b[i];
	ax/=m;ay/=m;
	while(clock()<=0.618520*CLOCKS_PER_SEC)sa();
	printf("%d",ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Pretests


Final Tests

Test #1:

score: 10
Accepted
time: 622ms
memory: 4112kb

input:

2 2 1000
0 2 1
0 -2 1
2 0
-2 0

output:

1

result:

ok single line: '1'

Test #2:

score: 10
Accepted
time: 616ms
memory: 4308kb

input:

2 2 20000
1 2 1
-1 2 1
100 0
-100 0

output:

2

result:

ok single line: '2'

Test #3:

score: 10
Accepted
time: 628ms
memory: 4364kb

input:

0 1000 2601
-9502 -15077
-1119 17787
-8732 15536
4106 17342
3119 -17547
-2511 17643
-16356 -7077
-2622 -17628
17018 -5293
-16486 -6768
-15424 -8927
10475 -14418
-17708 2011
-12281 12915
1788 -17731
-4269 17302
3723 17428
4971 17114
-16896 5666
-10384 -14484
-11532 13587
14740 -10016
1899 17721
14864...

output:

59

result:

ok single line: '59'

Test #4:

score: 10
Accepted
time: 628ms
memory: 4216kb

input:

0 1000 14012
-10655 14284
-16264 -7282
14894 -9784
7333 16242
-15252 -9215
3174 17536
17778 1230
13478 11659
-17341 4105
-9071 -15338
4702 -17189
11952 13218
-17820 -167
-17718 -1900
-15253 9215
-16690 6247
-17805 727
3559 -17462
-11952 -13219
2843 -17593
16332 7128
-10565 -14351
-3613 17450
1119 -1...

output:

318

result:

ok single line: '318'

Test #5:

score: 10
Accepted
time: 620ms
memory: 4128kb

input:

2 20 19444
5904 -5456 3563
7333 9372 990
1434 4553
1927 1738
-8247 -8381
-1794 6351
2524 -1684
866 -3411
-7818 -5768
-7970 1565
-410 -6944
-8504 7362
-8317 8371
4438 1929
5256 1405
-6064 2682
-2628 -9441
2024 -9304
-3302 -3905
-1538 968
-4750 -2769
-5514 -5987

output:

18

result:

ok single line: '18'

Test #6:

score: 10
Accepted
time: 620ms
memory: 4200kb

input:

4 10 100
0 0 3
10 0 3
10 10 3
0 10 3
0 4
0 5
0 6
5 3
5 -3
5 5
6 7
3 6
10 4
8 4

output:

5

result:

ok single line: '5'

Test #7:

score: 10
Accepted
time: 629ms
memory: 4376kb

input:

10 1000 20000
-5587 331 3162
8805 -8232 8782
3366 4104 4493
-5305 -8004 2302
-7453 -6293 155
-538 -2175 409
9799 2380 1318
-5472 6427 1721
-2375 5881 364
5887 8507 165
-1802 917
838 -2625
-3514 3119
-167 -1970
-1012 -4056
-2344 4824
-2444 2813
-1340 2703
478 368
77 -1185
-1377 2027
-1240 -4598
-3772...

output:

271

result:

ok single line: '271'

Test #8:

score: 10
Accepted
time: 630ms
memory: 4140kb

input:

2 1000 16150
-10000 -10000 14100
10000 10000 14100
3333 -4799
-4354 3599
-8876 6251
-9851 5264
-7191 7106
-4575 9544
-8083 6818
6221 -5651
-5445 6443
-6426 7819
-8562 9448
-8036 9808
9800 -5672
5248 -6016
-6086 6166
-4308 8454
-5607 9232
-8111 5905
6756 -4835
-5546 6422
4550 -5996
-6411 9521
8977 -8...

output:

382

result:

ok single line: '382'

Test #9:

score: 10
Accepted
time: 632ms
memory: 4244kb

input:

10 1000 12000
7774 -7292 277
-16899 12200 419
-13737 12239 281
3516 13024 339
11069 9719 226
8986 -12310 180
-2896 -14905 39
-6738 1023 441
13762 -10902 379
-9952 -14027 381
-19010 15026
226 15717
18288 -13326
11189 3641
3519 885
-96 -6965
-6604 -5458
11966 3815
2259 -16147
-6349 12858
-690 5316
-13...

output:

199

result:

ok single line: '199'

Test #10:

score: 10
Accepted
time: 629ms
memory: 4276kb

input:

10 1000 5000
-2453 4677 3712
582 -1746 1781
-3472 -7606 4236
5276 3448 2497
-9621 4956 621
-6452 -2823 399
-6601 89 644
8381 -3117 1692
-3872 -1862 1152
5211 -7138 451
1626 -3872
7022 -1034
-1188 8168
-6345 6845
6875 -5881
9273 9402
2898 2018
3538 9829
2234 -7514
9184 -9778
3099 -7097
-2617 -150
734...

output:

107

result:

ok single line: '107'