济南网站建设 unzz,新房网站建设公司,网站建设 核算,稿定设计app软件下载题目大意#xff1a;给你一个n (n300) 边形#xff0c;给出它所有的顶点坐标#xff0c;让你把它划分成n-2个三角形的花费最小值#xff0c;顶点 a 和 b 相连的花费为 abs(a.xb.x)*abs(a.yb.y)。 如果是凹多边形输出无解。 思路#xff1a;先跑个凸包判断是不是凸多边…题目大意给你一个n (n300) 边形给出它所有的顶点坐标让你把它划分成n-2个三角形的花费最小值顶点 a 和 b 相连的花费为 abs(a.xb.x)*abs(a.yb.y)。 如果是凹多边形输出无解。 思路先跑个凸包判断是不是凸多边形跑完之后点的顺序是逆时针的我们考虑区间dpdp[ i ][ j ]表示从顶点 i 沿多边形的边逆时针跑到 顶点 j 所形成的折线和 直线i-j所围成的多边形分割成小三角形所需要的花费。 状态转移方程 dp[ i ][ j ]min(dp[ i ][ j ] , dp[ i ][ k ]dp[ k ][ j ]cost[ i ][ k ]cost[ k ][ j ]); 如果j-i2 显然花费为0所以答案微dp[ 0 ][ n-1]。 1 #includebits/stdc.h2 using namespace std;3 const int N305;4 const int inf0x3f3f3f3f;5 int n,tot,dp[N][N],cost[N][N],mod;6 struct point7 {8 int x,y;9 point(int _x0,int _y0){x_x; y_y;}
10 point operator -(const point rhs)const
11 {
12 return point(x-rhs.x,y-rhs.y);
13 }
14 }p[N],cp[N];
15 typedef point vec;
16 int cross(const vec a,const vec b)
17 {
18 return (a.x*b.y)-(a.y*b.x);
19 }
20 int dis(point a,point b)
21 {
22 return (a.x-b.x)*(a.x-b.x)(a.y-b.y)*(a.y-b.y);
23 }
24 bool cmp(const point a,const point b)
25 {
26 int zcross(a-p[0],b-p[0]);
27 if(z0||(z0 dis(p[0],a)dis(p[0],b)))
28 return 1;
29 else return 0;
30 }
31 void get_cp()
32 {
33 int k0; tot0;
34 for(int i0;in;i)
35 if(p[i].yp[k].y || p[i].yp[k].y p[i].xp[k].x) ki;
36 swap(p[0],p[k]);
37 sort(p1,pn,cmp);
38 tot2,cp[0]p[0];cp[1]p[1];
39 for(int i2;in;i)
40 {
41 while(tot1 cross(cp[tot-2]-cp[tot-1],p[i]-cp[tot-1])0) tot--;
42 cp[tot]p[i];
43 }
44 }
45 void init()
46 {
47 memset(dp,-1,sizeof(dp));
48 memset(cost,0,sizeof(cost));
49 }
50 int solve(int l,int r)
51 {
52 if(dp[l][r]!-1) return dp[l][r];
53 if(r-l2) return 0;
54 dp[l][r]inf;
55 for(int kl1;kr-1;k)
56 dp[l][r]min(solve(l,k)solve(k,r)cost[l][k]cost[k][r],dp[l][r]);
57 return dp[l][r];
58 }
59 int main()
60 {
61 while(scanf(%d%d,n,mod)!EOF)
62 {
63 for(int i0;in;i) scanf(%d%d,p[i].x,p[i].y);
64 get_cp();
65 if(totn)
66 {
67 puts(I cant cut.);
68 continue;
69 }
70 init();
71 for(int i0;in;i)
72 for(int ji2;jn;j)
73 cost[i][j]cost[j][i]abs(cp[i].xcp[j].x)*abs(cp[i].ycp[j].y)%mod;
74
75 printf(%d\n,solve(0,n-1));
76 }
77
78 return 0;
79 } 转载于:https://www.cnblogs.com/CJLHY/p/8351294.html
