ZOJ 3537 （凸包 + 区间DP）（UNFINISHED）

#include "Head.cpp"

const int N = 10007;

int n, m;

struct Point{

    int x,y;

    bool operator < (const Point &com) const{

    	if(y != com.y) return y < com.y;

    	return x < com.x;

    }

}a[N];

int cost[N][N];

int f[N][N];

Point sta[407],tmp[407];

int top;

inline int cross(Point a,Point b,Point c){

    return (a.x - c.x) * (b.y - c.y) - (a.y - c.y) * (b.x - c.x);

}

inline int Graham(Point *a, int n){

	sort(a, a + n);

	sta[0] = a[0], sta[1] = a[1];

	top = 1;

	R(i, 0, n - 1){

		while(top && cross(sta[top], a[i], sta[top - 1]) >= 0) --top;

		sta[++top] = a[i];

	}

	int mid = top;

	nR(i,n - 2, 0){

		while(top > mid && cross(sta[top], a[i], sta[top - 1]) >= 0) --top;

		sta[++top] = a[i];

	}

	return top;

}

int Calc(Point a,Point b) {

	return abs((a.x + b.x) * (a.y+b.y)) % m;

}

int main(){

	FileOpen();

	while(scanf("%d%d", &n, &m) != EOF) {

		R(i,0, n - 1){

			io >> a[i].x >> a[i].y;

		}

		int tot = Graham(a,n);

		if(tot < n) {

            printf("I can't cut.\n");

            continue;

        }

        Fill(cost, 0);

        R(i,0,n - 1)

            R(j,i + 2, n - 1){

            	cost[i][j] = cost[j][i] = Calc(sta[i], sta[j]);

            }

        R(i,0, n - 1){

            R(j,0, n - 1){

                f[i][j] = 0x7fffffff;

            }

            f[i][(i + 1) % n] = 0;

        }

        nR(i,n-3,0)

            R(j,i + 2, n -1)

                R(k, i + 1, j - 1){

                	f[i][j] = Min(f[i][j], f[i][k] + f[k][j] + cost[i][k] + cost[k][j]);

                }

        printf("%d\n", f[0][n-1]);

	}

	return 0;

}

段错误什么鬼

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#define R(a,b,c) for(register int  a = (b); a <= (c); ++ a)

#define nR(a,b,c) for(register int  a = (b); a >= (c); -- a)

#define Max(a,b) ((a) > (b) ? (a) : (b))

#define Min(a,b) ((a) < (b) ? (a) : (b))

#define Fill(a,b) memset(a, b, sizeof(a))

#define Abs(a) ((a) < 0 ? -(a) : (a))

#define Swap(a,b) a^=b^=a^=b

#define ll long long

#define ON_DEBUG

#ifdef ON_DEBUG

#define D_e_Line printf("\n\n----------\n\n")

#define D_e(x)  cout << #x << " = " << x << endl

#define Pause() system("pause")

#define FileOpen() freopen("in.txt","r",stdin);

#else

#define D_e_Line ;

#define D_e(x)  ;

#define Pause() ;

#define FileOpen() ;

#endif

struct ios{

    template<typename ATP>ios& operator >> (ATP &x){

        x = 0; int f = 1; char c;

        for(c = getchar(); c < '0' || c > '9'; c = getchar()) if(c == '-')  f = -1;

        while(c >= '0' && c <= '9') x = x * 10 + (c ^ '0'), c = getchar();

        x*= f;

        return *this;

    }

}io;

using namespace std;

const int N = 10007;

int n, m;

struct Point{

    int x,y;

    bool operator < (const Point &com) const{

        if(y != com.y) return y < com.y;

        return x < com.x;

    }

}a[N];

int cost[N][N];

int f[N][N];

Point sta[407],tmp[407];

int top;

inline int cross(Point a,Point b,Point c){

    return (a.x - c.x) * (b.y - c.y) - (a.y - c.y) * (b.x - c.x);

}

inline int Graham(Point *a, int n){

    sort(a + 1, a + n + 1);

    sta[0] = a[1], sta[1] = a[2];

    top = 1;

    R(i, 1, n){

        while(top && cross(sta[top], a[i], sta[top - 1]) >= 0) --top;

        sta[++top] = a[i];

    }

    int mid = top;

    nR(i,n - 1, 1){

        while(top > mid && cross(sta[top], a[i], sta[top - 1]) >= 0) --top;

        sta[++top] = a[i];

    }

    return top;

}

int Calc(Point a,Point b) {

    return abs((a.x + b.x) * (a.y+b.y)) % m;

}

int main(){

//FileOpen();

    while(scanf("%d%d", &n, &m) != EOF) {

        R(i,1,n){

            io >> a[i].x >> a[i].y;

        }

        int tot = Graham(a, n);

        if(tot < n) {

            printf("I can't cut.\n");

            continue;

        }

        Fill(cost, 0);

        R(i,1,n)

            R(j,i + 2, n){

                cost[i][j] = cost[j][i] = Calc(sta[i], sta[j]);

            }

        R(i,1,n){

            R(j,1,n){

                f[i][j] = 0x3f3f3f3f;

            }

            f[i][i % n + 1] = 0;

        }

        nR(i,n - 2,1){

        	R(j,i + 2, n){

        		R(k, i + 1, j - 1){

                    f[i][j] = Min(f[i][j], f[i][k] + f[k][j] + cost[i][k] + cost[k][j]);

                }

        	}

        }

        printf("%d\n", f[1][n]);

    }

    return 0;

}

ZOJ 3537 （凸包 + 区间DP）（UNFINISHED）的相关教程结束。