有时间再修
P1337 [JSOI2004] 平衡点 / 吊打XXX
点击查看代码
#include<bits/stdc++.h>
#define cs const
#define il inline
#define ri register
#define pc(i) putchar(i)
#define Rd (T*(rand()*2-RAND_MAX))
using namespace std;
cs int N=1009;
cs long double D=0.92,eps=1e-14;
int n;
long double x[N],y[N],w[N],bx,by;
il long double calc(long double _x0,long double _y0)
{
long double re=0;
for(ri int i=1;i<=n;++i)
re+=sqrt((x[i]-_x0)*(x[i]-_x0)+(y[i]-_y0)*(y[i]-_y0))*w[i];
return re;
}
il void sa()
{
long double T,_x0,_y0,_x1,_y1,re,ans,bst; int times=1;
bst=ans=calc(bx/=n,by/=n); srand(time(0));
while(times--)
{
ans=bst,_x0=bx,_y0=by;
for(T=1e5;T>eps;T*=D)
{
_x1=_x0+Rd,_y1=_y0+Rd,re=calc(_x1,_y1);
if(bst>re) bst=re,bx=_x1,by=_y1;
if(ans>re||exp((ans-re)/T)>(long double)rand()/RAND_MAX)
ans=re,_x0=_x1,_y0=_y1;
}
}
printf("%.3Lf %.3Lf\n",bx,by);
}
signed main()
{
scanf("%d",&n);
for(ri int i=1;i<=n;++i)
scanf("%Lf%Lf%Lf",&x[i],&y[i],&w[i]),bx+=x[i],by+=y[i];
sa();
return 0;
}