RT

一开始一直不知道哪里错了，于是就用udebug上的数据和题解对拍，结果把卡时优化删掉后一发AC

话说udebug提供的数据输出是错的/kk

#include<bits/stdc++.h>
using namespace std;

const int N=5e4+10;

struct Node
{
	double x,y;
}pos[N];
int n;
double ansx,ansy,ans;

template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=x*10+c-'0';c=getchar();}
	x*=f;
}

void clear()
{
	ansx=ansy=0;
	ans=1e11;
}

double f(double x,double y)
{
	double res=0;
	for(int i=1;i<=n;++i)
	{
		double X=(x-pos[i].x),Y=(y-pos[i].y);
		res+=sqrt(X*X+Y*Y);
	}
	return res;
}

void SA()
{
	double T=2333;
	double x=ansx,y=ansy;
	while(T>=1e-10)
	{
		double nowx=x+((rand()<<1)-RAND_MAX)*T;
		double nowy=y+((rand()<<1)-RAND_MAX)*T;
		double now=f(nowx,nowy);
		double delta=now-ans;
		
		if(delta<0)
		{
			ansx=nowx,ansy=nowy;
			x=nowx,y=nowy;
			ans=now;
		}
		else if(exp(-delta/T)*RAND_MAX>rand())
		{
			x=nowx,y=nowy;
		}
		
		T*=0.997;
	}
}

void solve()
{
	ansx/=(double)n,ansy/=(double)n;
	ans=f(ansx,ansy);
	//while((double)clock()/CLOCKS_PER_SEC<=0.7){SA();}
	SA();
	return;
}

int main()
{
	srand(time(0));
	
	int T;
	read(T);
	
	for(int t=1;t<=T;++t)
	{
		read(n);
		clear();
		for(int i=1;i<=n;++i)
		{
			read(pos[i].x);read(pos[i].y);
			ansx+=pos[i].x,ansy+=pos[i].y;
		}
		
		solve();
		
		cout<<round(ans)<<'\n';
		if(t!=T)puts("");
	}
	
	return 0;
}