参考：https://www.cnblogs.com/zhuohan123/p/3237246.html
因为一c可以由1-a-b得出，所以删掉c，把a，b抽象成二维平面上的点。首先考虑一个客户需求能被哪些原料配出来：两个原料点连线上的点都可以，要是多个原料点，那么这些线的向量构成的凸包中的点都可以
所以得到了一个n三方算法：枚举每两个原料点，看是否所有需求点都在这条向量的半平面里，是则连1，然后Floyd求最小环即可
但是有非常多恶心的特判……
1.需求点重合为一点
2.需求点出现在两种原料点所在直线上的情况
#include<iostream>#include<cstdio>#include<cmath>using namespace std;const int N=505,inf=1e9;const double eps=1e-10;int m,n,a[N][N];double c;struct dian{ ???double x,y; ???dian(double X=0,double Y=0) ???{ ???????x=X,y=Y; ???} ???dian operator - (const dian &a) const ???{ ???????return dian(x-a.x,y-a.y); ???}}q[510],p[510];dian V(dian a,dian b){ ???return dian(b.x-a.x,b.y-a.y);}double cj(dian a,dian b){ ???return a.x*b.y-b.x*a.y;}bool ok(dian s,dian t,dian p){ ???return !((s.x>p.x&&t.x>p.x)||(s.x<p.x&&t.x<p.x)||(s.y>p.y&&t.y>p.y)||(s.y<p.y&&t.y<p.y));}int main(){ ???scanf("%d%d",&m,&n); ???for(int i=1;i<=m;i++) ???????scanf("%lf%lf%lf",&p[i].x,&p[i].y,&c); ???for(int i=1;i<=n;i++) ???????scanf("%lf%lf%lf",&q[i].x,&q[i].y,&c); ???for(int i=1;i<=m;i++) ???{ ???????bool flag=1; ???????for(int j=1;j<=n;j++) ???????????if(abs(p[i].x-q[j].x)>eps||abs(p[i].y-q[j].y)>eps) ???????????????flag=0; ???????if(flag) ???????{ ???????????printf("1\n"); ???????????return 0; ???????} ???} ???for(int i=1;i<=m;i++) ???????for(int j=1;j<=m;j++) ???????????a[i][j]=inf; ???for(int i=1;i<=m;i++) ???????for(int j=1;j<=m;j++) ???????if(i!=j) ???????{ ???????????if(abs(p[i].x-p[j].x)<eps&&abs(p[i].y-p[j].y)<eps) ???????????????continue ; ?????????????int can=1; ???????????for(int k=1;k<=n;k++) ???????????????if(cj(p[j]-p[i],q[k]-p[i])<-eps) ???????????????????can=0; ???????????if(can) ???????????{ ???????????????for(int k=1;k<=n;k++) ???????????????{ ???????????????????double cp=cj(p[j]-p[i],q[k]-p[i]); ???????????????????if(cp<eps&&cp>-eps&&(!ok(p[i],p[j],q[k]))) ???????????????????????can=0; ???????????????} ???????????} ???????????if(can) ???????????????a[i][j]=1; ???????} ???int ans=inf; ???for(int k=1;k<=m;k++) ???????for(int i=1;i<=m;i++) ???????????for(int j=1;j<=m;j++) ???????????????if(a[i][j]>a[i][k]+a[k][j]) ???????????????????a[i][j]=a[i][k]+a[k][j]; ???for(int i=1;i<=m;i++) ???????for(int j=1;j<=m;j++) ???????{ ???????????if(i!=j&&a[i][j]+a[j][i]<ans) ???????????????ans=a[i][j]+a[j][i]; ???????????if(i==j&&a[i][j]<ans) ???????????????ans=a[i][j]; ???????} ???printf("%d\n",ans==inf?-1:ans); ???return 0;}