PKU3684弾性衝突

この問題は、蟻本に載っている問題です。
蟻本はアルゴリズムを問題付きで解説していて非常に良い本なのですが、処理を短縮できる根拠を示してないことが多いです。
今回の記事は、その確認です。
この問題でひっかかったのは、R>0の時は、R=0の場合を計算して最後に2Riを足せば良いというところです。

このことを理解するために、まずは一秒遅れてボールが放たれるという条件を、同時に全てのボールが放たれると変更してみます。
ボールは一斉に落ちます。そして、周期分の時間経過すると一番下のボールが地面に衝突します。この時、同時に二番下のボールとも衝突します。そして、二番下のボールは三番下のボールともといった具合に、一番上まで連鎖が起こります。その結果、全てのボールが地面にぶつかった時と同じように動作します。つまり、この状態はR=0の場合を計算し、2Riのオフセットを足した場合と計算結果が同じになります。この例で理解して欲しいのは、衝突による速度の交換は一瞬であるということです。現実的な問題では、伝達の速度は光の速度を超えることはできないですが、それは無視してよいでしょう。
では、次に一秒ずらした場合を考えます。簡単にするために、ボールは2個にします。下のボールが地面に衝突して、上のボールと衝突する時を考えます。この時、上のボールの速度は下のボールの速度となり、下のボールの速度は上のボールの速度となります。この状態は、R=0の時と比較すると下のボールは2Ri上に、上のボールは2Ri下になります。
ソートした後に、2Riを足すことでこの状態を再現出来ます。

#include <vector>
#include <stdio.h>

using namespace std;

const double g = 10.0;

double
calc(int T,int H)
{
	if (T < 0) {
		return H;
	}
	double t = sqrt(2*H/g);
	int k= static_cast<int>(T/t);
	if ((k&1)==0) {
		double d = T-k*t;
		return H-g*d*d/2;
	} else {
		double d = k*t + t - T;
		return H-g*d*d/2;
	}
}

void
solve(int N,int H,int R,int T)
{
	vector<double> y(N);
	for (int i=0; i<N; ++i) {
		y[i] = calc(T-i,H);
	}
	sort(y.begin(), y.end());
	for (int i=0; i<N; ++i) {
		printf("%.2f%c",y[i]+2*R*i/100.0,i+1==N?'\n':' ');
	}
}

int
main(void) {
	int n;
	scanf("%d",&n);
	for (int i=0; i<n; ++i) {
		int N,H,R,T;
		scanf("%d %d %d %d",&N,&H,&R,&T);
		solve(N,H,R,T);
	}
}