A – Cake （+极角+凸包）

 #include<stdio.h>
 #include<string.h>
 #include<algorithm>
 #include<math.h>
 using namespace std; #define N 310
 #define inf 0x7fffffff struct point
 {
     int x,y;
 }dd[N]; int n,p;
 int dp[N][N];
 int cost[N][N];//边的花费 bool cmp(const point& a,const point &b){
     if(a.y == b.y)return a.x < b.x;
     return a.y < b.y;
 }   point save[],temp[];  int xmult(point p1,point p2,point p0){
     return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
 }   int Graham(point *p,int n){
     int i;
     sort(p,p + n,cmp);
     save[] = p[];
     save[] = p[];
     int top = ;
     for(i = ;i < n; i++){           while(top && xmult(save[top],p[i],save[top-]) >= ) top--;
         save[++top] = p[i];
     }
     int mid = top;
     for(i = n - ; i >= ; i--){
         while(top>mid&&xmult(save[top],p[i],save[top-]) >= ) top--;
         save[++top]=p[i];
     }
     return top;
 }   int min(int a,int b){return a<b?a:b;}; void init()
 {
     int i,j;
     for(i = ;i < n;i++){
         scanf("%d%d",&dd[i].x,&dd[i].y);
     }
     for(i = ;i < n;i++){
         dp[i][(i+)%n] = ;
         cost[i][(i+)%n] = cost[(i+)%n][i]=;
     }
 } int Dp()
 {
     int i,j,k;
     for(i = n-;i >= ;i--)//注意三个循环的方向
     for(j = i+;j < n;j++)//第一个循环从后往前 第二个循环从前往后是为了保证当前用到的状态都已经被计算过了 已经是最优的了
     for(k = i+;k < j;k++)
         dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j]+cost[i][k]+cost[k][j]);
     return dp[][n-];
 } int main()
 {
     int tot, i, j;
     while(scanf("%d%d", &n, &p)!=EOF)
     {
         init();
         tot    = Graham(dd,n);
         for(i = ;i < n;i++)
         for(j = i+;j < n;j++){
             dp[i][j] = inf;
             cost[i][j] = cost[j][i] = ((abs(save[i].x+save[j].x))*(abs(save[i].y+save[j].y)))%p;
         }
         //判断是否是凸多边形
         if(tot < n){
             printf("I can't cut.\n");
         }
         else{
             int ans = Dp();
             printf("%d\n",ans);
         }
     }
     return ;
 }