萌新刚学模拟退火
查看原帖
萌新刚学模拟退火
307535
Custlo0793楼主2021/8/14 16:29
#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贺的

2021/8/14 16:29
加载中...