zoj 3537 三角剖分 簡單區間DP

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4472

圖檔來自 ： http://blog.csdn.net/woshi250hua/article/details/7824433

題意：求将一個凸包切成若幹個三角形的最小代價

解法：上面的連結已經講的很詳細了，我就不多費口舌了

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int maxn = 310;
const double pi = acos(-1.0);
struct Point {
    int x, y;
    Point operator - (const Point& t) const {
        Point tmp;
        tmp.x = x - t.x;
        tmp.y = y - t.y;
        return tmp;
    }
    Point operator + (const Point& t) const {
        Point tmp;
        tmp.x = x + t.x;
        tmp.y = y + t.y;
        return tmp;
    }
    bool operator == (const Point& t) const {
        return abs(x-t.x) ==0 && abs(y-t.y) ==0;
    }
}GP; 
inline int Cross(Point a, Point b, Point c) {					// 叉積
	return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y); 
}
/***** 凸包 ****************************************************************************/
bool cmpyx(Point a, Point b) {										
	if ( a.y != b.y )
		return a.y < b.y;
	return a.x < b.x;
}
void Grahamxy(Point *p, int &n) {									// 水準序(住:兩倍空間)
	if ( n < 3 ) 
		return;
	int i, m=0, top=1;
	sort(p, p+n, cmpyx);	
	for (i=n; i < 2*n-1; i++)
		p[i] = p[2*n-2-i];
	for (i=2; i < 2*n-1; i++) {
		while ( top > m && Cross(p[top], p[i], p[top-1]) < 0 ) 
			top--;
		p[++top] = p[i];
		if ( i == n-1 )	m = top;
	}
	n = top;
}
int p;
int calc(Point a,Point b){
	return abs(a.x+b.x)*abs(a.y+b.y)%p;
}
Point pt[maxn];
int  dp[maxn][maxn];
int cost[maxn][maxn];
void Min(int &a,int b){
	if(a==-1 || a>b) a=b;
}
int main()
{
	int n;
	while(scanf("%d%d",&n,&p)!=EOF)
	{
		for(int i=0;i<n;i++) scanf("%d%d",&pt[i].x,&pt[i].y);
		int tot=n;
		Grahamxy(pt,tot);
		if(tot<n)
		{
			printf("I can't cut.\n");
			continue;
		}
	    memset(dp,-1,sizeof(dp));
		for(int i=0;i<n;i++) 
			for(int j=i+2;j<n;j++) cost[i][j]=cost[j][i]=calc(pt[i],pt[j]);
		for(int i=0;i<n;i++) dp[i][(i+1)%n]=0;
		for(int i=n-3;i>=0;i--)
		{
			for(int j=i+2;j<n;j++)
			{
				for(int k=i+1;k<j;k++)
				{
					Min(dp[i][j],dp[i][k]+dp[k][j]+cost[i][k]+cost[k][j]);
				}
			}
		}
		printf("%d\n",dp[0][n-1]);
	}
	return 0;
}