蒟蒻求助,一直在TLE
查看原帖
蒟蒻求助,一直在TLE
71558
AcerMo楼主2021/11/12 20:38
//By AcerMo
#include<ctime>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int M=1050;
int n;
int x[M],y[M],w[M];
double lx,ly;
double sx,sy;
double ans,t;
double dt=0.886;
inline void read(int &x)
{
	x=0;int f=1;
	char c=getchar();
	while (!isdigit(c)) f=c=='-'?-1:f;
	while (isdigit(c)) x=x*10+c-'0',c=getchar();
	return (void)(x*=f);
}
inline double qre(double a,double b)
{
	double sum=0;
	for (int i=1;i<=n;i++)
	{
		double dx=a-x[i];
		double dy=b-y[i];
		sum+=(sqrt(dx*dx+dy*dy)*w[i]);
	}
	return sum;
}
inline void SA()
{
	t=2000;
	while (t>1e-12)
	{
		double tx=lx+(rand()*2-RAND_MAX)*t;
		double ty=ly+(rand()*2-RAND_MAX)*t;
		double tans=qre(tx,ty);
		double dans=tans-ans;
		if (dans<0) 
		{
			lx=tx;ly=ty;
			ans=tans;
		}
		else if (exp(-dans/t)*RAND_MAX>rand())
		lx=tx,ly=ty;
		t*=dt;
	}
	return ;
}
inline void start()
{
	sx=sx/n;sy=sy/n;
	ans=qre(sx,sy);
	srand((unsigned)time(NULL));SA();
	srand((unsigned)time(NULL));SA();
	srand((unsigned)time(NULL));SA();
	SA();SA();
	return ;
}
signed main()
{
	read(n);
	for (int i=1;i<=n;i++)
	{
		read(x[i]);sx+=x[i];
		read(y[i]);sy+=y[i];
		read(w[i]);	
	} 
	start();
	printf("%.3lf %.3lf",lx,ly);
	return 0;
}
2021/11/12 20:38
加载中...