2850 Stacking Cylinders

問題概要

半径が1の円柱を積み上げる。
n+1列目の円柱は全て、n列目の円柱のちょうど二つに接している。

円柱は、円柱が列に一つだけになるまで積み上げられる。
1列目の円柱のx座標が与えられたとき、一番上の円柱の中心の座標を求めよ。

解法

ひとつ上の円柱の中心は、下の二つの円柱の中心をA,Bとすれば、
A,Bをそれぞれ中心とする半径2の円二つの交点（の上のほう）である。

円柱が1つになるまで繰り返し列の円柱の座標を全部求める。

ソースコード

x座標はincreasing orderと書かれていなかったような気がしたので一応ソートした。

bool cmp(const P &a,const P &b){
	return real(a)!=real(b)?real(a)<real(b):imag(a)<imag(b);
}
P func(P a,P b)
{
	P d=b-a,m=(a+b)/P(2,0);
	double h=sqrt(4.0-norm(d/P(2,0)));
	return m+d/abs(d)*P(0,h);
}
int main()
{
	int CS; scanf("%d",&CS);
	rep(cs,CS)
	{
		P C[10],D[10],*c=C,*d=D;
		int n; scanf("%d",&n);
		rep(i,n)
		{
			double x; scanf("%lf",&x);
			c[i]=P(x,1);
		}
		sort(c,c+n,cmp);
		rep(i,n-1)
		{
			rep(j,n-i-1)d[j]=func(c[j],c[j+1]);
			swap(c,d);
		}
		printf("%d: %.4f %.4f\n",cs+1,real(c[0]),imag(c[0]));
	}
	return 0;
}