萌新求助模拟退火

rt

#include<bits/stdc++.h>
#define db long double
#define dw 0.995
#define For(i,a,b) for(int i(a);i<=b;++i)
#define foR(i,a,b) for(int i(a);i>=b;--i)
using namespace std;
inline void read(int &x){
	x=0;char ch;bool w=0;ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=1; ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	if(w)x=-1*x;
}
inline void print(int x){
	if(x<0){putchar('-');print(-x);return ;}
	if(x>9)print(x/10);putchar(x%10+'0');
}
const int N=2e4+67;
int n,T,X[N],Y[N];
db sumx,sumy,ansx,ansy,qwqx,qwqy;
db dis(db ax,db ay,db bx,db by){
	return sqrt((bx-ax)*(bx-ax)+(by-ay)*(by-ay));
}
void init(){
	ansx=0;ansy=0;
	sumx=0;sumy=0;
}
db Query(db x,db y){
	db wow=0.0;
	For(i,1,n){
		wow+=dis(x,y,X[i],Y[i]);
	}
	return wow;
}
void SA(){
	db t=2022;
	ansx=qwqx;ansy=qwqy;
	while(t>1e-15){
		db x=ansx+(rand()<<1-RAND_MAX)*t;
		db y=ansy+(rand()<<1-RAND_MAX)*t;
		db del=Query(x,y)-Query(ansx,ansy);
		if(del<0){
			ansx=x;ansy=y;
		}
		else{
			if(exp( (-del)/t)*RAND_MAX > rand()){
				ansx=x;ansy=y;
			}
		}
		t*=dw;
	}
}
void HQ(){
	qwqx=sumx/n;qwqy=sumy/n;
	For(i,1,7)SA();
}
signed main(){
	srand(time(0));
	read(T);
	For(www,1,T)
	{
		init();
		read(n);
		For(i,1,n){
			read(X[i]);read(Y[i]);
			sumx+=X[i];sumy+=Y[i];
		}
		HQ();
		int sb=Query(ansx,ansy);
		printf("%d\n",(int)Query(ansx,ansy));
		if(www!=T)cout<<"\n";
	}
}