Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-04-01SRM355 (Practice)

SRM 355 Tetrahedron

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

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

  • 幾何。点をA, B, C, Dと置く
    • まずどれかの3点について、三角形が作れないなら "NO"
    • それ以外の場合、A(0, 0) B(dist[A][B], 0) として、C, Dの座標を求める
      • このとき余弦定理を使うと楽に求められる
    • CDの最小最大を求め、dist[C][D]と比べて検証する
public class Tetrahedron {
	double EPS = 1e-11;
	
	public String exists(String[] d) {
		int[][] dist = new int[4][4];
		for (int from = 0; from <= 3; from++) {
			String[] line = d[from].split(" ");
			for (int to = 0; to <= 3; to++) {
				dist[from][to] = Integer.valueOf(line[to]);
			}
		}
		for (int i = 0; i < 4; ++i) {
			for (int j = 0; j < 4; ++j) {
				for (int k = 0; k < 4; ++k) {
					if (dist[i][j] + dist[j][k] < dist[i][k]) {
						return "NO";
					}
				}
			}
		}

		double coscab = (double)(dist[0][1] * dist[0][1] + dist[0][2] * dist[0][2] - dist[1][2] * dist[1][2]) / (2.0d * dist[0][1] * dist[0][2]);
		double cx = dist[0][2] * coscab;
		double cy = Math.sqrt(dist[0][2] * dist[0][2] - cx * cx);
		
		double cosdab = (double)(dist[0][1] * dist[0][1] + dist[0][3] * dist[0][3] - dist[1][3] * dist[1][3]) / (2.0d * dist[0][1] * dist[0][3]);
		double dx = dist[0][3] * cosdab;
		double dy = Math.sqrt(dist[0][3] * dist[0][3] - dx * dx);

		if (Math.hypot(cx - dx, cy - dy) - EPS < dist[2][3] && Math.hypot(cx - dx, cy + dy) + EPS > dist[2][3]) {
			return "YES";
		}
		return "NO";
	}
}