PKU 2194 Stacking Cylinders
http://poj.org/problem?id=2194
円筒を上に積み重ねていくときの、一番上の円筒の中心座標を求めろというような問題。
座標計算を下からやっていく。
入力が順番通りでないということに気づかなくてサンプルが合わないことに悩みました。
pair<double,double> in[20][20]; main(){ int n; while(cin>>n,n){ rep(i,n){ cin>>in[0][i].F; in[0][i].S=1; } sort(in[0],in[0]+n); for(int i=1;i<n;++i){ for(int j=0;j<n-i;++j){ double v1x=in[i-1][j+1].F-in[i-1][j].F; double v1y=in[i-1][j+1].S-in[i-1][j].S; double r=sqrt(v1x*v1x+v1y*v1y); double th=acos(r/4); in[i][j].F=(v1x*cos(th)-v1y*sin(th))*2/r+in[i-1][j].F; in[i][j].S=(v1x*sin(th)+v1y*cos(th))*2/r+in[i-1][j].S; } } printf("%.4f %.4f\n",in[n-1][0].F,in[n-1][0].S); } }