Hatena::Grouptopcoder

TopCoder戦記

研究開発者・ellerのTopCoder挑戦記録。言語は主にJavaを使用しています。ドキュメンテーションコメントはSubmit完了後、ブログ掲載前に補完したものです。

2009-09-25SRM449 DIV1

SRM449 DIV1 Level One(250pt.)

| 00:11

http://www.topcoder.com/stat?c=problem_statement&pm=10548&rd=13903

3頂点が格子点上にあり、2辺の長さが√Aおよび√Bである三角形を考える。この三角形が取りうる最大の面積を求めよ。

1点を座標平面上の原点に固定し、残り2点を第1象限・第2象限に配置する考え方で解答。最大でも(√A*√B)の計算量で済み、TLEにはなりにくいでしょう。桁溢れに気をつければ比較的簡単に解答することができます。

なお面積を求める方法としては、辺の長さだけで済むヘロンの公式を採用しています。

// 120.72 pt.

public class MaxTriangle {
	public double calculateArea(int A, int B) {
		double result = -1.0D;
		double a = Math.sqrt(A);	// 小文字a,b,cは辺の長さ
		double b = Math.sqrt(B);
		
		for (int x = 1; x <= Math.floor(a); ++x) {
			int y = (int) Math.floor(Math.sqrt(A - x * x));
			if ((double) y == Math.sqrt(A - x * x) && x * x + y * y == A) {
				for (int yy = 1; yy <= Math.floor(b); ++yy) {
					int xx = (int) Math.floor(Math.sqrt(B - yy * yy));
					if ((double) xx == Math.sqrt(B - yy * yy) && xx * xx + yy * yy == B) {
						long X = xx + x, Y = yy - y;	// 桁溢れを防ぐため、事前にlongへキャスト

						double c = Math.sqrt(X * X + Y * Y);
						result = Math.max(result, calcArea(a, b, c));
					}
				}
			}
		}
		return result;
	}

	/**
	 * ヘロンの公式によって三角形の面積を求める
	 * @param a 1辺の長さ
	 * @param b 1辺の長さ
	 * @param c 1辺の長さ
	 * @return 三角形の面積
	 */
	private double calcArea(double a, double b, double c) {
		double s = (a + b + c) / 2.0D;
		return Math.sqrt(s * (s - a) * (s - b) * (s - c));
	}
}