Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-08SRM386 (Practice)

SRM 386 PolygonCover

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

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

  • げぇっ、幾何ゲーだ
  • 方針を検討
    • よく読むと幾何要素はそこまででもない
    • 全ての点を最低1つの多角形に使う時、面積の最小値を求める問題のようだ
    • 2分探索?いや違う。
    • 点の数が15しかないから・・・ それを使うんだろう
      • bitDPかな
    • でも計算量がヤバイ気がする
      • 三角形だけでも 2^15*(15^3) = 90,000,000ぐらい。
      • 四角形以上だと全然間に合わないだろう
  • うーん
    • 待てよ、これ作る多角形は全部三角形と仮定していいんじゃないか?
      • 任意の4点について、四角形の面積と三角形の面積x2 を比べた時、必ず 三角形x2 の面積が小さくなる作り方がある
        • 長方形の場合は特殊で、両者の面積がイコールになる
      • 5点以上についても多分同様なはず・・・
    • 三角形だけなら計算量的に余裕だろう。
  • 実装
    • dfsをゴリゴリ作る。
    • 任意の3点の三角形の面積を前計算しておこう
  • できた。サンプル通った。
    • 最大ケース(ランダム15点)でテスト。
    • OK
  • 提出
    • 直後、三点が一直線上に並ぶ場合を考慮してないことに気づく。
    • 大丈夫な気もするけど、念のため確認したい・・・
    • でも制約見ると、
      • No three points represented by x and y will lie on a common line.
    • と書いてある。よかった

システムテスト

  • WAを食らう。あれ!?
    • 誤差死してるっぽい
  • 三角形の面積の求め方。
    • ヘロンの公式を使ったが、座標が整数で与えられるときはもっと精度がいい方法が存在する!当たり前だね
    • てか |a| <= 1000 でも誤差死してしまうのか・・・
      • これは今後challengeに使えそうなので覚えておこう

import java.util.Arrays;

public class PolygonCover {
	double[] dx;
	double[] dy;

	double EPS = 0.000000001d;
	double INF = 100000000000.0d;
	double[] memo;

	double[][][] area;
	
	int len;
	
	public double area(int p1, int p2, int p3) {
	    return Math.abs((dx[p2] - dx[p1]) * (dy[p3] - dy[p1]) - (dx[p3] - dx[p1]) * (dy[p2] - dy[p1])) / 2.0d;
	}

	public double area(double ax, double ay, double bx, double by, double cx, double cy) {
		double ab = Math.sqrt((ax-bx)*(ax-bx)+(ay-by)*(ay-by));
		double bc = Math.sqrt((bx-cx)*(bx-cx)+(by-cy)*(by-cy));
		double ca = Math.sqrt((cx-ax)*(cx-ax)+(cy-ay)*(cy-ay));
		double s = (ab + bc + ca) / 2.0d;
		return Math.sqrt(s*(s-ab)*(s-bc)*(s-ca));
	}

	public double dfs(int ptn) {
		if (ptn == (1<<len)-1) {
			return 0.0d;
		}
		if (memo[ptn] < INF) {
			return memo[ptn];
		}
		
		double min = INF;
		for (int a = 0 ; a < len ; a++) {
			for (int b = a+1 ; b < len ; b++) {
				for (int c = b+1 ; c < len ; c++) {
					int nptn = ptn | (1<<a) | (1<<b) | (1<<c);
					if (ptn == nptn) {
						continue;
					}
					min = Math.min(min, area[a][b][c] + dfs(nptn));
				}
			}
		}
		memo[ptn] = Math.min(memo[ptn], min);
		return min;
	}
	
	
	public double getArea(int[] x, int[] y) {
		len = x.length;
		dx = new double[len];
		dy = new double[len];
		
		for (int i = 0 ; i < len ; i++) {
			dx[i] = x[i];
			dy[i] = y[i];
		}
		
		area = new double[len][len][len];
		for (int a = 0 ; a < len ; a++) {
			for (int b = a+1 ; b < len ; b++) {
				for (int c = b+1 ; c < len ; c++) {
					area[a][b][c] = area(a, b, c);
				}
			}
		}
		memo = new double[1<<len];
		Arrays.fill(memo, INF);
		
		return dfs(0);
	}

}