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);
		}
};