可以发现比重只用考虑两维，因此可以把原料看成平面上的点，若干个原料能合成的区域就是凸包。 这样问题变成了求一个点集 A 的最小子集，使得围成的凸包包含另一个点集B的所有点。可以枚举 A 中的边，如果b中的所有点都在它左侧就连一条有向边。最后floyd找最小环就是答案。
#include<cstdio> #include<cmath> #include<algorithm> using namespace std; const double eps=1e-10; const int maxn=510,oo=0x3f3f3f3f; int cmp(double x) { if (x>eps) return 1; if (fabs(x)<=eps) return 0; return -1; } struct Vector { double x,y; void rd() { scanf("%lf%lf%*lf",&x,&y); } Vector operator + (const Vector &v) const { return (Vector){x+v.x,y+v.y}; } Vector operator - (const Vector &v) const { return (Vector){x-v.x,y-v.y}; } }a[maxn],b[maxn]; typedef Vector Point; double dot(Vector v,Vector u) { return v.x*u.x+v.y*u.y; } double cross(Vector v,Vector u) { return v.x*u.y-v.y*u.x; } struct Segment { Point a,b; }; int m,n,dis[maxn][maxn]; int check(Segment s) { int x; for (int i=1;i<=n;i++) { x=cmp(cross(s.b-s.a,b[i]-s.a)); if (x==1||(x==0&& cmp(dot(b[i]-s.a,b[i]-s.b))==1)) return 0; } return 1; } int main() { int ans=oo; scanf("%d%d",&m,&n); for (int i=1;i<=m;i++) a[i].rd(); for (int i=1;i<=n;i++) b[i].rd(); for (int i=1;i<=m;i++) for (int j=1;j<=m;j++) dis[i][j]=check((Segment){a[i],a[j]})?1:oo; for (int k=1;k<=m;k++) for (int i=1;i<=m;i++) for (int j=1;j<=m;j++) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); for (int i=1;i<=m;i++) ans=min(ans,dis[i][i]); printf("%d\n",ans==oo?-1:ans); }