ZOJ 3537 Cake 凸包+区间dp

#include<bits/stdc++.h>
#define ll long long 
#define INF 0x3f3f3f3f
using namespace std;
const double eps = 1e-10;
double dcmp(double x) {
    if(fabs(x) < eps) return 0;
    else return x < 0 ? -1 : 1;
}
 
struct Point {
    double x, y;
    Point(double x=0, double y=0):x(x),y(y) {}
};
vector<Point> v;

Point operator - ( const Point &A ,const Point &B) {
    return Point(A.x-B.x, A.y-B.y);
}

bool operator == (const Point& p1, const Point& p2) {
    return p1.x == p2.x && p1.y == p2.y;
}
bool operator < (const Point& p1, const Point& p2) {
    return p1.x < p2.x || (p1.x == p2.x && p1.y < p2.y);
}

double Cross(const Point& A, const Point& B) {
    return A.x*B.y - A.y*B.x;
}

 
double Dot(const Point& A, const Point& B) {
    return A.x*B.x + A.y*B.y;
}
int cross(Point p0,Point p1,Point p2) //计算叉积  p0p1 X p0p2
{
    return (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x);
}
double dis(Point p1,Point p2)  //计算 p1p2的 距离
{
    return sqrt((double)(p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y));
}
bool cmp(Point p1,Point p2) //极角排序函数 ， 角度相同则距离小的在前面
{
    int tmp=cross(v[0],p1,p2);
    if(tmp>0) return true;
    else if(tmp==0&&dis(v[0],p1)<dis(v[0],p2)) return true;
    else return false;
}

vector<Point> ConvexHull(vector<Point> p) {
    // 预处理，删除重复点
    sort(p.begin(), p.end());
    p.erase(unique(p.begin(), p.end()), p.end());
 
    int n = p.size();
    int m = 0;
    vector<Point> ch(n+1);
    for(int i = 0; i < n; i++) {
        while(m > 1 && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) <= 0) m--;
        ch[m++] = p[i];
    }
    int k = m;
    for(int i = n-2; i >= 0; i--) {
        while(m > k && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) <= 0) m--;
        ch[m++] = p[i];
    }
    if(n > 1) m--;
    ch.resize(m);
    return ch;
}
int f[305][305];
int dp[305][305];
	vector<Point> s;

int main(){
	
	int n,m;
	int  xx,yy;
	while(scanf("%d%d",&n,&m)>0){
		for(int i=0;i<n;i++){
			scanf("%d%d",&xx,&yy);
			v.push_back({xx,yy});
		}
		s = ConvexHull(v);
		if(s.size()!=n ){
			cout << "I can't cut.\n";
			v.clear();
			continue;
		}
		else{
			sizeof(f,0,sizeof(f));
            for (int i=0; i<n; i++)
            {
                for (int j=i+2; j<n; j++)
                    f[i][j] = f[j][i] =  (  ((ll)fabs(s[i].x + s[j].x) ) * ((ll)fabs(s[i].y + s[j].y)  ))%m;
            }
            for (int i=0; i<n; i++)
            {
                for (int j=0; j<n; j++)
                    dp[i][j] = INF;
                dp[i][(i+1)%n]=0;
            }
            for (int i=n-3; i>=0; i--)//区间dp求解
            {
                for (int j=i+2; j<n; j++)
                {
                    for (int k=i+1; k<j; k++)
                    {
                        dp[i][j]=min(dp[i][j], dp[i][k]+dp[k][j]+f[i][k]+f[k][j]);
                    }
                }
            }
            cout<<dp[0][n-1]<<endl;

		}
		v.clear();
		s.clear();
	}
}


/*
4 100
1 1
2 1
1 2
2 2
*/