#include<bits/stdc++.h>
#define rep(i,l,r) for(register int i=l;i<=r;i++)
#define per(i,r,l) for(register int i=r;i>=l;i--)
using namespace std;
int n,m;
const int N=114514;
const double delta=0.99;
double sx,sy,sn,r;
struct arc {
double x,y,z;
}b[N];
struct sb {
double x,y;
}hum[N];
double dis(double x,double y,double s,double t) {
return sqrt((s-x)*(s-x)+(t-y)*(t-y));
}
int calc(double x,double y) {
int res=0; double k=r;
rep(i,1,n) {
double lenth=dis(x,y,b[i].x,b[i].y);
k=min(k,lenth-b[i].z);
}
rep(i,1,m) {
double lenth=dis(x,y,hum[i].x,hum[i].y);
if(lenth<=k) res++;
}
return res;
}
void SA() {
double temp=3000;
while(temp>1e-16) {
double p=sx+(rand()*2-RAND_MAX)*temp,q=sy+(rand()*2-RAND_MAX)*temp;
double upd=calc(p,q); double del=upd-sn;
if(del>0) sx=p,sy=q,sn=upd;
else if(exp(-upd/temp)*RAND_MAX<rand()) sx=p,sy=q;
temp*=delta;
}
}
void prepare() {
srand(114514+1919810); srand(rand()+20070606);
srand(rand());
srand(rand());
srand(rand());
cin>>n>>m>>r;
rep(i,1,n) cin>>b[i].x>>b[i].y>>b[i].z;
rep(i,1,m) {
cin>>hum[i].x>>hum[i].y;
sx+=hum[i].x,sy+=hum[i].y;
} sx/=m,sy/=m; sn=calc(sx,sy);
return ;
} he
int main() {
prepare(); rep(i,1,55) SA(); cout<<sn;
}
用的是lmpp之前在一个帖子下的参数,TLE了。
AC是我测试最后一篇solution贺的