[JSOI2004]平衡点

题面在这里

题意

...见链接吧

sol

在此发一篇模拟退火的题解

不得不说luogu的数据真是太良心啦

一句话解释模拟退火:在一个慢慢缩小的范围内随机状态寻找最优解，当转移状态更优时直接接受，当当前状态更优时以一定概率\((exp(dlt/T))\)接受

具体实现请参照代码

#include<bits/stdc++.h>

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<iomanip>

#include<cstring>

#include<vector>

#include<cstdio>

#include<string>

#include<bitset>

#include<cmath>

#include<queue>

#include<stack>

#include<map>

#include<set>

#define sqr(x) ((x)*(x))

#define pb push_back

#define RG register

#define il inline

using namespace std;

const int mod=1e9+7;

const int N=1010;

typedef unsigned long long ull;

typedef vector<int>VI;

typedef long long ll;

typedef double dd;

il ll read(){

	RG ll data=0,w=1;RG char ch=getchar();

	while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();

	if(ch=='-')w=-1,ch=getchar();

	while(ch<='9'&&ch>='0')data=data*10+ch-48,ch=getchar();

	return data*w;

}

int n;dd mn;

struct point{dd x,y,w;}p[N],ans,now;

il dd make(){return rand()%100000/100000.00;}

il dd dis(point a,point b){return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}

il dd calc(point x){

	RG dd ret=0;

	for(RG int i=1;i<=n;i++)

		ret+=p[i].w*dis(x,p[i]);

	return ret;

}

il void SA(point x){

	RG dd T=1e6;

	while(T>1e-3){//退火过程

		now.x=ans.x+T*(2*make()-1);

		now.y=ans.y+T*(2*make()-1);

		double dlt=calc(ans)-calc(now);

		if(dlt>0||exp(dlt/T)>make())ans=now;

		T*=0.996;

	}

	for(int i=1;i<=50000;++i)//最后在一定范围内搜寻到局部最优解

	{

		now.x=ans.x+T*(2*make()-1);

		now.y=ans.y+T*(2*make()-1);

		if(calc(ans)-calc(now)>0)ans=now;

	}

}

int main()

{

	srand(time(NULL)+rand());

	n=read();

	for(RG int i=1;i<=n;i++)

		scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].w);

	ans=(point){make(),make(),0};mn=ans.w=calc(ans);

	SA(ans);

	printf("%.3lf %.3lf\n",ans.x,ans.y);

	return 0;

}

考试骗分，模拟退火，你值得拥有！