最优三角剖分 - Zoj3537

首先要知道什么是凸包，数学中的凸包和ACM中常说的凸包貌似概念有点对不上

ACM，遇到一个点集S时，会利用求凸包的算法,

将S中的部分点依次相连，形成一个凸包(多边形)，点集S中的点要么在多边形上，要么在多边形内

我的板板:

//4_21-凸包-Graham
bool cmp(PII A, PII B)
{	return A.first == B.first ? A.second < B.second : A.first < B.first;}
//计算从AB向量到BC向量 是否是逆时针转弯
int getturn(PII A, PII B, PII C)
{
	PII AR1(B.first - A.first, B.second - A.second), AR2(C.first - B.first, C.second - B.second);
	return (AR1.first*AR2.second) - (AR1.second*AR2.first);
}
PII save[maxn];
//save[1,return值-1]存顶点编号，因为是转一圈，所以返回值是顶点数+1
int Graham(PII p[], int n)
{
	sort(p+1, p+1 + n, cmp);
	int top = 0;
	RE2(i,n)
	{
		while (top >= 2 && getturn(save[top-1],save[top], p[i]) < 0)
			top--;
		save[++top] = p[i];
	}
	int mid = top;
	for (int i = n - 1; i >= 1; i--) {
		while (top > mid && getturn(save[top - 1], save[top], p[i]) < 0)top--;
		save[++top] = p[i];
	}
	return top;
}

接下来，看如果凸包用到了所有的点，就有解，

接下来要想到，一条边和一个顶点可以确定一个三角形，如果只是想着DP,会为三角形顶点的这个区间不好划分而烦恼

但是，做三角划分是，可以想，1-n这条边肯定是在一个三角形以内的，这个三角形肯定还有另外一个顶点是[2,n-1]中的一个

是哪个呢，设它为k,那么k确定时，多边形被划分为[1,k]顶点在内的多边形，[k,n]顶点在内的多边形，三角形(1,k,n)

这样这个多边形的解可以用两个子多边形的解加上三角形的贡献算出来，并且两个子多边形都是连续的区间，可以表示出来