Codeforces #34 (div2) E "Collisions"

問題：http://codeforces.com/contest/34/problem/E

プラクティス．
ボールの位置，速度，重量が与えられ，ある時間になったときの各ボールの座標を求める問題．
衝突を考慮し，衝突する場合は規定の式を用いる．
本番中に方針は分かってたものの実装が間に合わず未提出．

最初に座標の位置でソートする．これ以降ボールの順番はいくら衝突しようが変わらないはず．
次に位置と速度から隣り合うボール同士の中で一番最初にぶつかる時間を計算し，各ボールの位置と，衝突する場合はその速度を更新する．これを求めたい時間まで繰り返す．
最後に入力されたボールの順番にソートしなおして出力．

浮動小数点の誤差を考慮することに慣れてなかったため，いろいろと引っかかってた．テストケースが公開されてたのは非常に助かった．
http://codeforces.com/blog/entry/746

import java.util.*;

public class E_Collisions {
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int n = s.nextInt(), T = s.nextInt();
		List<double[]> m = new ArrayList<double[]>();
		for (int i = 0; i < n; ++i) {
			double[] d = new double[4];
			d[0] = i;
			for (int j = 1; j < 4; ++j) {
				d[j] = s.nextInt();
			}
			m.add(d);
		}
		Collections.sort(m, new Comparator<double[]>() {
			@Override
			public int compare(double[] o1, double[] o2) {
				return Double.compare(o1[1], o2[1]);
			}
		});
		for (double t=0; Double.compare(t,T)<0;) {
			List<Double>q=new ArrayList<Double>();
			q.add(T-t);
			for (int i = 0; i < n - 1; ++i) {
				// 隣接するボール同士が衝突する時間を求める
				double[]x=m.get(i),y=m.get(i+1);
				if(x[2]-y[2]>0&&Math.abs(x[1]-y[1])>1e-5){
					q.add((y[1]-x[1])/(x[2]-y[2]));
				}
			}
			Collections.sort(q);
			double t1=q.get(0);
			// t1秒後におけるすべてのボールの位置を更新．
			for(double[] d : m){
				d[1] += d[2] * t1;
			}
			// 接触するボールは規定の式を用いて速度も更新．
			for(int  i = 0; i < m.size()-1; ++i){
				double[] x=m.get(i),y=m.get(i+1);
				double xv=x[2], yv=y[2];
				if(Math.abs(x[1]-y[1])<1e-5){
					xv = v(x[2],x[3],y[2],y[3]);
					yv = v(y[2],y[3],x[2],x[3]);
				}
				x[2] = xv;
				y[2] = yv;
				
			}
			t += t1;
		}
		Collections.sort(m, new Comparator<double[]>() {
			@Override
			public int compare(double[] o1, double[] o2) {
				return Double.compare(o1[0], o2[0]);
			}
		});
		for(double[]d:m){
			System.out.println(d[1]);
		}
	}
	
	static private double v(double xv, double xm, double yv, double ym){
		return ((xm-ym)*xv+2*ym*yv)/(xm+ym);
	}
}