QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#798973 | #6212. 炸弹攻击 | Grain_Depot08 | 100 ✓ | 632ms | 4376kb | C++14 | 1001b | 2024-12-04 19:49:26 | 2024-12-04 19:49:27 |
Judging History
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'