2420 A Star not a Tree?
問題概要
n個の点の座標が与えられる。
これらの点からのユークリッド距離の和が最小になる点を求め、
和の最小値を整数に四捨五入して出力せよ。
解法
多変数関数の最小値なので準ニュートン法を用いてみた。
準ニュートン法の部分のコードはspaghetti source参照。
各点の座標をX[i],Y[i]とする。最小化したいユークリッド距離の和は、
f(x,y)=Σ[i=1,n]hypot(X[i]-x,Y[i]-y)
であり、その微分は、
grad f(x,y)=(Σ(-2x+2X[i])/hypot(), Σ(-2y+2Y[i])/hypot())
と書ける。
初期値は適当に重心を用いてみた。
なんか最近数値計算の問題を良く見るのでシンプソン法とかもライブラリ化しておいた方が良い気がしてきたなあ。
ソースコード
int n; double X[100],Y[100]; weight f(array x){ weight ret=0; rep(i,n)ret+=hypot(X[i]-x[0],Y[i]-x[1]); return ret; } array df(array x){ array ret(2,0); rep(i,n){ weight d=hypot(X[i]-x[0],Y[i]-x[1]); ret[0]+=2*(x[0]-X[i])/d; ret[1]+=2*(x[1]-Y[i])/d; } return ret; } int main(){ scanf("%d",&n); array x(2); rep(i,n)scanf("%lf%lf",X+i,Y+i),x[0]+=X[i],x[1]+=Y[i]; x[0]/=n; x[1]/=n; x=quasi_newton(x); printf("%.0f\n",f(x)); return 0; }