SRM386div1 medium
凸な図形=三角形の集まりなので
rec(どの座標を使ったか(=mask)、今どの座標か(=k))は
kを含む三角形を(i,j,k)の面積をsとすると
s+rec(maskにi,j,kを追加した物,k+1)
の内最小化のものを返せば良い。
あとはそれをメモ化再帰して終わり。
三角形の面積を求めるにはヘロンの公式が便利。
#include <vector> #include <cmath> #include <cfloat> using namespace std; double cache[(1<<15)][20]; class PolygonCover { public: int n; vector<double> x; vector<double> y; double S(int v1,int v2,int v3) { double e1,e2,e3,s,x1,y1,x2,y2,x3,y3; x1=x[v1]-x[v2]; y1=y[v1]-y[v2]; x2=x[v2]-x[v3]; y2=y[v2]-y[v3]; x3=x[v3]-x[v1]; y3=y[v3]-y[v1]; e1=sqrt(x1*x1+y1*y1); e2=sqrt(x2*x2+y2*y2); e3=sqrt(x3*x3+y3*y3); s=(e1+e2+e3)/2; return sqrt(s*(s-e1)*(s-e2)*(s-e3)); } double rec(int mask,int k) { double &r=cache[mask][k]; if(-1<r) return r; else if(k==n) r=0.0; else if(mask & (1<<k)) r=rec(mask,k+1); else { r=DBL_MAX; for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) if(i!=k && j!=k) { int m=(mask|(1<<i)|(1<<j)|(1<<k)); r=min(r,S(i,j,k)+rec(m,k+1)); } } return r; } double getArea(vector<int> _x, vector<int> _y) { x.clear(); y.clear(); n=_x.size(); for(int i=0;i<n;i++) { x.push_back(_x[i]); y.push_back(_y[i]); } for(int i=0;i<(1<<n);i++) for(int j=0;j<n;j++) cache[i][j]=-2; return rec(0,0); } };