Codeforces 106 E. Space Rescuers

問題

n個の惑星があり、それぞれの座標は(x[i],y[i],z[i])である。
最も遠い惑星への距離が最小になるような点の座標を求めよ。

制約条件

n≦100
座標の絶対値≦10^4

方針

山登り法で収束するまでまわす。

近傍は、それぞれの惑星への方向で、
最も遠い惑星へ近づくように移動する。

ソースコード

int n;

void run()
{
        cin>>n;
        vector<double> x(n),y(n),z(n);
        rep(i,n)cin>>x[i]>>y[i]>>z[i];
        
        double x0=0,y0=0,z0=0, l=0.999;
        rep(it,100000){
                double mx=0; int mni;
                rep(i,n){
                        #define sq(x) (x)*(x)
                        double d=sqrt(sq(x[i]-x0)+sq(y[i]-y0)+sq(z[i]-z0));
                        if(d>mx)mx=d, mni=i;
                }
                x0+=(x[mni]-x0)*l;
                y0+=(y[mni]-y0)*l;
                z0+=(z[mni]-z0)*l;
                l*=0.999;
        }
        printf("%.9f %.9f %.9f\n",x0,y0,z0);
}