萌新求调模拟退火
查看原帖
萌新求调模拟退火
271736
Daidly楼主2022/8/17 17:04

RT,最高 4040

已经用过毕生乱搞绝学了。

#include<bits/stdc++.h>
using namespace std;

inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c<='9'&&c>='0'){
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}

inline void print(int x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)print(x/10);
	putchar(x%10^48);
}

const int N=15,M=1e3+5;
const double MAX_TIME=0.95,eps=1e-6;
int n,m,X=1,Y=1;
int ans;
double R,ansx,ansy;
struct node{
	double x,y,r;
}p[N];
struct enemy{
	double x,y;
}a[M];

int calc(double x,double y){
	double r=1e9;
	for(int i=1;i<=n;++i){
		r=min(r,sqrt((p[i].x-x)*(p[i].x-x)+(p[i].y-y)*(p[i].y-y))-p[i].r);
	}
	r=min(R,r);
	int num=0;
	for(int i=1;i<=m;++i){
		if(sqrt((a[i].x-x)*(a[i].x-x)+(a[i].y-y)*(a[i].y-y))<=r)num++;
	}
	return num;
}

double rand1(double l,double r){
	return (double)rand()/RAND_MAX*(r-l+1)+l;
}

void sa(){
	double T=3000;
	while(T>eps){
		double nx=rand1(ansx-T,ansx+T);
		double ny=rand1(ansy-T,ansy+T);
		int nans=calc(nx,ny);
		if(nans>ans)ans=nans,ansx=nx,ansy=ny;
		else if(exp((nans-ans)/T)>rand1(0,1))ansx=nx,ansy=ny;
		T*=0.99;
	}
}

int main(){
	n=read(),m=read(),cin>>R;
	for(int i=1;i<=n;++i)cin>>p[i].x>>p[i].y>>p[i].r;
	for(int i=1;i<=m;++i)cin>>a[i].x>>a[i].y;
	for(int i=1;i<=m*100;++i){
		int x=rand()%m+1;
		int y=rand()%m+1;
		swap(a[x],a[y]);
	}
	for(int i=1;i<=m;++i){
		if((double)clock()/CLOCKS_PER_SEC>MAX_TIME)break;
		ansx=a[i].x,ansy=a[i].y;
		ans=max(ans,calc(ansx,ansy));
		sa(),sa(),sa();
	}
	print(ans);
	return 0;
}
2022/8/17 17:04
加载中...