照着 OIwiki 写的,交了 41 次没过。
#include<bits/stdc++.h>
using namespace std;
int n,x[1005],y[1005],w[1005];
double ansx,ansy,dis;
double Rand(){
return(double)rand()/RAND_MAX*2.00-1.00;
}
double ds(double xx,double yy){
double res=0;
for(int i=1;i<=n;i++){
double dx=x[i]-xx,dy=y[i]-yy;
res+=sqrt(dx*dx+dy*dy)*w[i];
}
if (res<dis)dis=res,ansx=xx,ansy=yy;
return res;
}
void mnth(){
double t=100000000,nx=ansx,ny=ansy;
while(t>1e-18){
double dx=nx+t*Rand(),dy=ny+t*Rand(),delta=ds(dx,dy)-ds(nx,ny);
if (exp(-delta/t)>(Rand()+1/2.00))nx=dx,ny=dy;
t*=0.998;
}
for(int i=1;i<=1000;i++) {
double dx=ansx+t*Rand();
double dy=ansy+t*Rand();
ds(dx,dy);
}
}
int main(){
srand(time(0));
cin>>n;
for(int i=1;i<=n;i++){
scanf("%d%d%d",&x[i],&y[i],&w[i]);
ansx+=x[i],ansy+=y[i];
}
ansx/=n,ansy/=n,dis=ds(ansx,ansy);
mnth();mnth();mnth();mnth();mnth();mnth();
printf("%.3lf %.3lf\n",ansx,ansy);
}