SRM 386 Div1 Medium PolygonCover

問題

XY座標上で点が与えられる。全ての点が少なくとも1つ以上の多角形に属するように多角形を配置する。それらの面積の和が最小となるように配置し、その和を返せ。多角形の頂点は常に与えられた点の上にしか置くことはできない。与えられた点は多角形の辺上、もしくは内部にあるとき属しているものとする。

やりかた

またしてもbitDP。
与えられた点は常に多角形の頂点に重なるように置くほうが面積が小さくて済むし、かつ三角形のみで覆っていくほうが面積は小さくて済む。
あとは以下の様な状態のbitDPを行えばいい。

dp[S]:=（すでに覆われた頂点を1、まだの頂点を0とするビット状態で実現できる最小面積）

以下ソース。

double dp[1 << 15];

class PolygonCover {
public:
  int N;
  vector<int> X, Y;
  double area(int i, int j, int k){//i,j,k番目の頂点でできる三角の面積
    double vy = Y[i] - Y[j], vx = X[i] - X[j];
    double uy = Y[i] - Y[k], ux = X[i] - X[k];
    return 0.5 * fabs(vx * uy - vy * ux);
  }
  double rec(int S){
    if(S == (1 << N) - 1) return 0.0;
    if(dp[S] > EPS) return dp[S];

    double ret = 1e100;
    for(int i = 0; i < N; i++){
      for(int j = 0; j < N; j++){
	for(int k = 0; k < N; k++){
          //3頂点ともすでに覆われている場合は無視
	  if((S >> i & 1) && (S >> j & 1) && (S >> k & 1)) continue;
          //3つの頂点はすべて異なる必要がある
	  if(i == j || j == k || k == i) continue;
	  ret = min(ret, area(i, j, k) + rec(S | 1 << i | 1 << j | 1 << k));
	}
      }
    }
    return dp[S] = ret;
  }
  double getArea(vector <int> x, vector <int> y) {
    N = x.size();
    memset(dp, -1, sizeof(dp));
    X = x, Y = y;
    return rec(0);
  }
};

再帰なし

double dp[1 << 15];

class PolygonCover {
public:
  int N;
  vector<int> X, Y;
  double area(int i, int j, int k){
    double vy = Y[i] - Y[j], vx = X[i] - X[j];
    double uy = Y[i] - Y[k], ux = X[i] - X[k];
    return 0.5 * fabs(vx * uy - vy * ux);
  }
  double getArea(vector <int> x, vector <int> y) {
    N = x.size();
    fill(dp, dp + (1 << 15), 1e100);
    X = x, Y = y;
    
    dp[0] = 0;
    for(int S = 0; S < 1 << N; S++){
      for(int i = 0; i < N; i++){
	if(S >> i & 1) continue;
	for(int j = 0; j < N; j++){
	  for(int k = 0; k < N; k++){
	    if(i == j || j == k || k == i) continue;
	    dp[S | 1 << i | 1 << j | 1 << k]
	      = min(dp[S | 1 << i | 1 << j | 1 << k], dp[S] + area(i, j, k));
	  }
	}
      }
    }
    return dp[(1 << N) - 1];
  }
};