题解
- 先判个凸多边形,然后最优三角剖分,DP[i][j]=min(DP[i][j,DP[i][k]+DP[k][j]+cst[i][k]+cst[k][j])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
using namespace std;
const int N=407;
const ll inf=0x3f3f3f3f;
int n,p,cnt;
ll dp[N][N],x[N],y[N],res[N],id[N],cst[N][N];
template <typename T>inline void read(T &x){
x=0;char c;int sign=1;
do{c=getchar(); if(c=='-')sign=-1;}while(c<'0'||c>'9');
do{x=x*10+c-'0'; c=getchar();}while(c>='0'&&c<='9');
x*=sign;
}
inline ll cul(int a,int b,int c){return abs(x[a]+x[b])*abs(y[a]+y[b])%p+abs(x[c]+x[b])*abs(y[c]+y[b])%p;}
inline int cmp(int a,int b){return y[a]==y[b]?x[a]<x[b]:y[a]<y[b];}
inline int crp(int x1,int y1,int x2,int y2){return x1*y2-x2*y1;}
inline int init(){
cnt=0;
rep(i,1,n)read(x[i]),read(y[i]),id[i]=i;sort(id+1,id+n+1,cmp);
rep(i,1,n){
while(cnt>1&&crp(x[res[cnt]]-x[res[cnt-1]],y[res[cnt]]-y[res[cnt-1]],x[id[i]]-x[res[cnt-1]],y[id[i]]-y[res[cnt-1]])<=0)--cnt;
res[++cnt]=id[i];
}
int tmp=cnt;
repd(i,n-1,1){
while(cnt>tmp&&crp(x[res[cnt]]-x[res[cnt-1]],y[res[cnt]]-y[res[cnt-1]],x[id[i]]-x[res[cnt-1]],y[id[i]]-y[res[cnt-1]])<=0)--cnt;
res[++cnt]=id[i];
}
return cnt==n+1;
}
inline void solve(){
memset(dp,0x3f,sizeof(dp));
memset(cst,0,sizeof(cst));
rep(i,1,n-1)dp[i][i+1]=0;
rep(i,1,n)rep(j,i+2,n)
cst[i][j]=cst[j][i]=abs(x[res[i]]+x[res[j]])*abs(y[res[i]]+y[res[j]])%p;
repd(i,n-2,1)rep(j,i+2,n)rep(k,i+1,j-1)dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+cst[i][k]+cst[k][j]);
}
int main(){
while(~scanf("%d%d",&n,&p)){
if(!init()){puts("I can't cut.");continue;}
solve();
printf("%d\n",dp[1][n]);
}
return 0;
}