膜你退火求调
查看原帖
膜你退火求调
242524
JRzyh楼主2021/6/2 20:59

假如是参数问题我就滚回去调参了qq_emoji: kk

总炸第五个点

#include<bits/stdc++.h>
#define EL out[wz++]='\n'
#define SP out[wz++]=' '
#define Yes out[wz++]='Y',out[wz++]='e',out[wz++]='s'
#define YES out[wz++]='Y',out[wz++]='E',out[wz++]='S'
#define No out[wz++]='N',out[wz++]='o'
#define NO out[wz++]='N',out[wz++]='O'
using namespace std;
char ibuf[900<<20],*re,out[900<<20];
int wz;
inline int read()
{
    register int u=0,op=1;
    while(*re<48||*re>57)
	{
		if(*re=='-')op=-1;
		re++;
	}
    while(*re>=48&&*re<=57)
        u=u*10+*re++-48;
    return u*op;
}
inline long long readll()
{
    register long long u=0,op=1;
    while(*re<48||*re>57)
	{
		if(*re=='-')op=-1;
		re++;
	}
    while(*re>=48&&*re<=57)
        u=u*10+*re++-48;
    return u*op;
}
void print(long long x)
{
    if(x<0){out[wz++]='-';x=-x;}
	if(x>9)print(x/10);
    out[wz++]=x%10+'0';
}
void print(int x)
{
    if(x<0){out[wz++]='-';x=-x;}
	if(x>9)print(x/10);
    out[wz++]=x%10+'0';
}
void print(string s)
{
	 for(int i=0;i<s.size();i++)out[wz++]=s[i];
}
void print(char* s)
{
 	 for(int i=0;s[i]!='\0';i++)out[wz++]=s[i];
}
const double dt=0.9,eps=1e-14;
double best=0x3f3f3f3f,ax,ay;
struct things
{
	double x,y,w;
}a[1008];
int n;
inline double dis(double x1,double y1,double x2,double y2)
{
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
double f(double x,double y)
{
	double ans=0;
	for(register int i=1;i<=n;i++)
	{
		ans+=dis(x,y,a[i].x,a[i].y)*a[i].w;
	}
	return ans;
}
void tem()
{
	double ans=best;
	double x=ax,dx=0,y=ay,dy=0;
	double t=5000;
	while(t>eps)
	{
		dx=t*(rand()*2-RAND_MAX);
		dy=t*(rand()*2-RAND_MAX);
		double x0=x+dx,y0=y+dy,f0=f(x0,y0);
		if(best>f0)best=f0,ax=x0,ay=y0;//best使其不会错过最优解。 
		if(f0<ans||exp((ans-f0)/t)*RAND_MAX>rand())
		{
			y=y0;x=x0;ans=f0;
		}
		t*=dt;
	}
}
void SA()
{
	while(clock()<CLOCKS_PER_SEC*0.9)tem();
}
int main()
{
	fread(re=ibuf,1,900<<20,stdin);
	double sumx=0,sumy=0;
	srand(19260817);
	n=read();
	for(register int i=1;i<=n;i++)
	{
		a[i].x=read();
		a[i].y=read();
		a[i].w=read(); 
		sumx+=a[i].x;
		sumy+=a[i].y;
	}
	ax=sumx/n;
	ay=sumy/n;
	best=f(ax,ay); 
	SA();
	double rx=ax,ry=ay;
	for(register double i=rx-0.01;i<=rx+0.01;i+=0.001)//对答案进行微小扰动,求更优 
	{
		for(register double j=ry-0.01;j<=ry+0.01;j+=0.001)
		{
			double f0=0;
			for(register int k=1;k<=n;k++)
			{
				f0+=dis(i,j,a[k].x,a[k].y)*a[k].w;
				if(f0>=best)goto AwA; 
			}
			best=f0,ax=i,ay=j;
			AwA:;
		}
	}
	printf("%.3lf %.3lf",ax,ay);
 	return 0;
}
2021/6/2 20:59
加载中...