Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-04-05SRM347 (Practice)

SRM 347 Aircraft

|  SRM 347 Aircraft - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 347 Aircraft - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7741

  • ふつーに三分探索しようとした
    • 式が間違ってて答えが合わなかった。ひどい
  • editorial見ると二次方程式を解くのがいいらしい。なんと
public class Aircraft {
	long RR;
	public String nearMiss(int[] p1, int[] v1, int[] p2, int[] v2, int R) {
		RR = 1L * R * R;
		
		long[] np = new long[3];
		long[] dv = new long[3];
		for (int i = 0 ; i < 3 ; i++) {
			np[i] = p2[i] - p1[i];
			dv[i] = v2[i] - v1[i];
		}
		
		long A = 0, B = 0, C = 0;
		for (int i = 0 ; i < 3 ; i++) {
			A += dv[i] * dv[i];
			B += 2 * np[i] * dv[i];
			C += np[i] * np[i];
		}
		if (C <= RR) {
			return "YES";
		}
		if (A == 0 || B >= 0) {
			return "NO";
		}
		if (B * B - 4 * A * (C - R * R) >= 0) {
			return "YES";
		}
		return "NO";
	}
}