rt

发现我写得模拟退火正确性不高啊

如下 P1337 代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
inline int read(){
	int res=0,f=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') {res=res*10+(c-'0');c=getchar();}
	return res*f;
}
const int N=1005;
const double Delta=0.996,Eps=1e-14;
const double l=-1e4,r=1e4;
const double D[]={1,-1};
int n;
double res=1e18,ax,ay;
struct node{
	int x,y,w;
}a[N];
mt19937 rnd(time(0));
double f(double x,double y){
	double res=0;
	for (int i=1;i<=n;i++){
		double dx=(x-a[i].x)*(x-a[i].x),dy=(y-a[i].y)*(y-a[i].y);
		double dis=sqrt(dx+dy);
		res+=dis*a[i].w;
	}
	return res;
}
void solve(){
	double T=2333,x=0,y=0;
	double now=f(x,y),ans=now;
	while (T>Eps){
		double _x=D[rnd()%2]*T+x,_y=D[rnd()%2]*T+y;
		if (_x>=l&&_x<=r&&_y>=l&&_y<=r){
			double ths=f(_x,_y),val=now-ths;
			ans=min(ans,ths);
			if (val>Eps) x=_x,y=_y,now=ths;
			else if (exp(val/T)>rnd()) x=_x,y=_y,now=ths;
		}
		T*=Delta;
	}
	if (ans<res) ax=x,ay=y,res=ans;
}
signed main(){
	n=read();
	for (int i=1;i<=n;i++) a[i]={read(),read(),read()};
	double timer=clock();
	while (clock()-timer<=CLOCKS_PER_SEC*0.9)
		solve();
	printf("%.3lf %.3lf",ax,ay);
	return 0;
}

小号测了 $10$ 次只过了 $4$ 次，其余 WA