A

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 #include<math.h>
 5 using namespace std;
 6 
 7 #define N 310
 8 #define inf 0x7fffffff
 9 
10 struct point 
11 {
12     int x,y;
13 }dd[N];
14 
15 int n,p;
16 int dp[N][N];
17 int cost[N][N];//边的花费
18 
19 bool cmp(const point& a,const point &b){    
20     if(a.y == b.y)return a.x < b.x;  
21     return a.y < b.y;  
22 }  
23 
24 point save[400],temp[400]; 
25 
26 int xmult(point p1,point p2,point p0){    
27     return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);  
28 }  
29 
30 int Graham(point *p,int n){
31     int i;  
32     sort(p,p + n,cmp);  
33     save[0] = p[0];  
34     save[1] = p[1];  
35     int top = 1;  
36     for(i = 0;i < n; i++){  
37   
38         while(top && xmult(save[top],p[i],save[top-1]) >= 0) top--;  
39         save[++top] = p[i];  
40     }  
41     int mid = top;  
42     for(i = n - 2; i >= 0; i--){
43         while(top>mid&&xmult(save[top],p[i],save[top-1]) >= 0) top--;  
44         save[++top]=p[i];  
45     }  
46     return top;  
47 }  
48 
49 int min(int a,int b){return a<b?a:b;};
50 
51 void init()
52 {
53     int i,j;
54     for(i = 0;i < n;i++){
55         scanf("%d%d",&dd[i].x,&dd[i].y);
56     }
57     for(i = 0;i < n;i++){
58         dp[i][(i+1)%n] = 0;
59         cost[i][(i+1)%n] = cost[(i+1)%n][i]=0;
60     }
61 }
62 
63 int Dp()
64 {
65     int i,j,k;
66     for(i = n-3;i >= 0;i--)//注意三个循环的方向
67     for(j = i+2;j < n;j++)//第一个循环从后往前 第二个循环从前往后是为了保证当前用到的状态都已经被计算过了 已经是最优的了
68     for(k = i+1;k < j;k++)
69         dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j]+cost[i][k]+cost[k][j]);
70     return dp[0][n-1];
71 }
72 
73 int main()
74 {
75     int tot, i, j;
76     while(scanf("%d%d", &n, &p)!=EOF)
77     {
78         init();
79         tot    = Graham(dd,n);
80         for(i = 0;i < n;i++)
81         for(j = i+2;j < n;j++){
82             dp[i][j] = inf;
83             cost[i][j] = cost[j][i] = ((abs(save[i].x+save[j].x))*(abs(save[i].y+save[j].y)))%p;
84         }
85         //判断是否是凸多边形
86         if(tot < n){
87             printf("I can't cut.
");
88         }
89         else{
90             int ans = Dp();
91             printf("%d
",ans);
92         }
93     }
94     return 0;
95 }