作者:-依小冷_217 | 来源:互联网 | 2023-10-10 14:29
首先这题应该改名叫吊打出题人题目大意:给定n个质点,求重心这n个质点的重心满足Σ(重心到点i的距离)*g[i]最小模拟退火的裸题尼玛交了两篇死活过不去各种改参数最后发现是我的INF
首先这题应该改名叫吊打出题人
题目大意:给定n个质点,求重心
这n个质点的重心满足Σ(重心到点i的距离)*g[i]最小
模拟退火的裸题
尼玛交了两篇 死活过不去 各种改参数 最后发现是我的INF不够大 尼玛!
这题INF开0x3f妥妥过不去。。。起码要max_of _long_long附近才可以
最后写了10188MS,BZOJ倒数第一……这也是种艺术啊0.0
#include
#include
#include
#include
#include
#define M 10100
using namespace std;
struct point{
double x,y,g;
}points[M],ans;
int n;
double minans=23333333333333333ll;
double dis(const point &x,const point &y)
{
return sqrt( (x.x-y.x)*(x.x-y.x) + (x.y-y.y)*(x.y-y.y) );
}
double Judge(const point &p)
{
int i;
double re=0;
for(i=1;i<=n;i++)
re+=points[i].g*dis(p,points[i]);
if(reans=p,minans=re;
return re;
}
double Rand()
{
return rand()%1000/1000.0;
}
void SA(double T)
{
int i;
point Now=ans;
while(T>0.001)
{
point Neo;
Neo.x=Now.x+T*(Rand()*2-1);
Neo.y=Now.y+T*(Rand()*2-1);
double dE = Judge(Now) - Judge(Neo) ;
if( dE > 0 || exp(dE/T)>Rand() )
Now=Neo;
T*=0.993;
}
for(i=1;i<=1000;i++)
{
point Neo;
Neo.x=ans.x+T*(Rand()*2-1);
Neo.y=ans.y+T*(Rand()*2-1);
Judge(Neo);
}
}
int main()
{
int i;
srand(19970815);
cin>>n;
for(i=1;i<=n;i++)
{
scanf("%lf%lf%lf",&points[i].x,&points[i].y,&points[i].g);
ans.x+=points[i].x;
ans.y+=points[i].y;
}
ans.x/=n;
ans.y/=n;
SA( 1000000 );
printf("%.3lf %.3lf\n",ans.x,ans.y);
}