P1433 吃奶酪 题解报告

#include
#define ll long long
#define lim 0.004//停止温度 
#define d 0.996//降温幅度 
using namespace std;
ll n;
ll now[18];
ll now1,now2;
double nowz,ans=1e9;
double sx[18],sy[18];
double dis(ll w,ll z)
{
	return sqrt((sx[w]-sx[z])*(sx[w]-sx[z])+(sy[w]-sy[z])*(sy[w]-sy[z]));//两点间距离计算公式 
}
double calc()
{
	double res=0;
	for(int i=1;i<=n;i++) res+=dis(now[i],now[i-1]);//计算值 
	return res; 
}
void ghost_fire()
{
	srand(rand());//玄学 
	for(int i=1;i<=n;i++) now[i]=i;//初始值 
	double T=10000;
	while(T>lim)
	{
		now1=rand()%n+1;
		now2=rand()%n+1;//产生随机点 
		swap(now[now1],now[now2]);//交换 
		nowz=calc();
		double del=nowz-ans;
		if(del<0) ans=nowz;
		else if(exp(-del/T)*50000>(double)rand()/RAND_MAX){//此题各个答案之间误差较小，可以*50000来增大替换解的概率 
		}
		else swap(now[now1],now[now2]);
		T*=d;
	}
}
void Cros_Fire()
{
	for(int i=1;i<=1e9&&(double)clock()/CLOCKS_PER_SEC<=0.99;i++) ghost_fire();//运行量过大，用时间函数锁时 
} 
int read()//lj快读 
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)
	{
		cin>>sx[i]>>sy[i];//一定要要注意，用scanf或cin，让lj快读卡了我半小时 
	}
	Cros_Fire();
	printf("%.2f",ans);//保留后两位 
	return 0;
}