可以联想到矩阵的线性相关。
根据题意得出所求的合金应该是在材料的一个凸包内。
而要求是凸包的边尽量少。
建图跑floyd最短路。
每次判断点是否都在线段左侧，第二个判断是判断共线时点是否在线段上。
By：大奕哥
1 #include<bits/stdc++.h> 2 #define eps 1e-7 3 #define N 510 4 using namespace std; 5 struct node{ 6 ????double x,y,z; 7 }a[N],b[N]; 8 node vet(node a,node b) 9 {10 ????node c;c.x=a.x-b.x;c.y=a.y-b.y;11 ????return c;12 }13 double xmul(node a,node b){return a.x*b.y-b.x*a.y;}14 double pmul(node a,node b){return a.x*b.x+a.y*b.y;}15 int n,m,ans,f[N][N];16 void floyd()17 {18 ????ans=1e9;19 ????for(int k=1;k<=n;++k)20 ????????for(int i=1;i<=n;++i)21 ????????????for(int j=1;j<=n;++j)22 ????????????????f[i][j]=min(f[i][j],f[i][k]+f[k][j]);23 ????for(int i=1;i<=n;++i)ans=min(ans,f[i][i]);24 }25 int main()26 {27 ????scanf("%d%d",&n,&m);28 ????memset(f,0x3f,sizeof(f));29 ????for(int i=1;i<=n;++i)scanf("%lf%lf%lf",&a[i].x,&a[i].y,&a[i].z);30 ????for(int i=1;i<=m;++i)scanf("%lf%lf%lf",&b[i].x,&b[i].y,&b[i].z);31 ????for(int i=1;i<=n;++i)32 ????for(int j=1;j<=n;++j)33 ????{34 ????????bool flag=0;35 ????????for(int k=1;k<=m;++k)36 ????????{37 ????????????double cross=xmul(vet(a[i],b[k]),vet(a[j],b[k]));38 ????????????if(cross>eps){flag=1;break;}39 ????????????if(fabs(cross)<eps&&pmul(vet(a[i],b[k]),vet(a[j],b[k]))>eps)40 ????????????{flag=1;break;}41 ????????}42 ????????if(!flag)f[i][j]=1;43 ????}44 ????floyd();45 ????if(ans==1e9)puts("-1");46 ????else printf("%d",ans);47 ????return 0;48 }BZOJ1027 [JSOI2007]合金
原文地址：https://www.cnblogs.com/nbwzyzngyl/p/8323605.html