TopCoder SRM 386 Div1 Medium PolygonCover

問題

n個の点が与えられる。それぞれの座標は(x[i],y[i])である。
これらの点を、いくつかの凸多角形で覆う。
それぞれの多角形は、与えられた点を結んだものでなくてはならない。

全ての点を覆うために必要な凸多角形の面積の和を求めよ。
面積A,Bの二つの多角形が重なっているときも、面積の和はA+Bと数えるものとする。

制約条件

n≦15

方針

点の集合を一つ決めると、
それを覆うために必要な最も小さい多角形は、それらの集合の凸包になる。

あらかじめ、全ての点の集合に対して凸包の面積を求めておく。
dp[i]を、iで表される点の集合を覆うために必要な面積の最小値とすると、
すべてのiの部分集合について、dp[i]=min(dp[j]+dp[i^j])
が成り立つので、部分集合を更新するようなDPをすればよい。

iとjに重なりがある場合あるが、それは前処理で、
集合sに対して、sを含むような集合で、sだけを囲うよりも面積が小さいものがあったら、
その面積に置き換えることをすればよい。

ソースコード

凸包、多角形の面積はspaghetti sourceの。

double dp[1<<15];

class PolygonCover {
  public:
  double getArea(vector <int> x, vector <int> y) {
    int n=x.size();
    rep(i,1<<n){
      dp[i]=INF;
      if(__builtin_popcount(i)<3)continue;
      G g;
      rep(j,n)if(i&1<<j)g.pb(P(x[j],y[j]));
      dp[i]=area2(convex_hull(g));
    }
    rep(i,1<<n)for(int j=i;j;j=j-1&i)dp[j]=min(dp[j],dp[i]);
    rep(i,1<<n)for(int j=i;j;j=j-1&i)dp[i]=min(dp[i],dp[j]+dp[i^j]);
    
    return dp[(1<<n)-1]/2;
  }
};