求调模拟退火
查看原帖
求调模拟退火
224192
蒟蒻且菜鸡楼主2022/11/18 16:06

开O2八十分

#include<bits/stdc++.h>
using namespace std;
int n,m,r;
double ansx,ansy,ans;
struct node{
	int x,y,r;
}a[100001];
struct nod{
	int p,q;
}b[100001];
double dis(double x,double y,double xx,double yy)
{
	return sqrt((x-xx)*(x-xx)+(y-yy)*(y-yy));
}
long long dist(double x,double y)
{
	double d=r;
	long long res=0;
	for(int i=1;i<=n;i++)
	{
		d=fmin(d,dis(a[i].x,a[i].y,x,y)-a[i].r);
	}
	for(int i=1;i<=m;i++)
	  if(dis(x,y,b[i].p,b[i].q)<=d) res++;
	return res;
}
void SA()
{
	double T=3022;
	double x=ansx,y=ansy;
	while(T>1e-10)
	{
		double X=x+(rand()<<1-RAND_MAX)*T;
		double Y=y+(rand()<<1-RAND_MAX)*T;
		long long nowans=dist(X,Y);
		double delta=nowans-ans;
		//cout<<nowans;
		if(delta>0)
		{
			ans=nowans;
			ansx=X;
			ansy=Y;
			x=X;
			y=Y;
		}
		else if(exp(delta/T)*RAND_MAX<rand())
		{
		    ansx=X;
			ansy=Y;
			//ans=nowans;
		}
		T*=0.996;
	}
}
int main()
{
	srand(20070322);
	cin>>n>>m>>r;
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].r);
		ansx+=a[i].x;
		ansy+=a[i].y;
	}
	for(int i=1;i<=m;i++) scanf("%d%d",&b[i].p,&b[i].q);
	ansx/=(n*1.0);
	ansy/=(n*1.0);
	ans=dist(ansx,ansy);
	for(int i=1;i<=70;i++) SA();
	printf("%0.lf",ans);
	return 0;
}
2022/11/18 16:06
加载中...