题意：某公司加工一种由铁、铝、锡组成的合金。他们的工作很简单。首先进口一些铁铝锡合金原材料，不同种类的原材料中铁铝锡的比重不同。然后，将每种原材料取出一定量，经过融解、混合，得到新的合金。新的合金的铁铝锡比重为用户所需要的比重。 现在，用户给出了n种他们需要的合金，以及每种合金中铁铝锡的比重。公司希望能够订购最少种类的原材料，并且使用这些原材料可以加工出用户需要的所有种类的合金。 原材料种类n和需要合金数m≤500，每个合金的铁/铝/锡比例a+b+c=1
【分析】 计算几何 参考 http://blog.csdn.net/popoqqq/article/details/40539273 关键在于叉积判断点在直线的哪一侧与floyd求最小环 主函数里有个很迷的地方，我加了if(i!=j) 就错掉了，不加就对了…这精度卡的有点丧啊…
【代码】
//BZOJ 1027 合金 #include<iostream> #include<cstring> #include<cstdio> #define eps 1e-6 #define inf 1e9+7 #define M(a) memset(a,0,sizeof a) #define fo(i,j,k) for(i=j;i<=k;i++) using namespace std; const int mxn=505; int n,m,ans=inf; int f[mxn][mxn]; double x[mxn],y[mxn],a[mxn],b[mxn],l,r; inline int floyd() { int i,j,k; fo(k,1,m) fo(i,1,m) if(f[i][k]<inf) fo(j,1,m) f[i][j]=min(f[i][j],f[i][k]+f[k][j]); fo(i,1,m) ans=min(ans,f[i][i]); if(ans==inf) return -1; return ans; } int main() { int i,j,k; scanf("%d%d",&m,&n); fo(i,1,m) scanf("%lf%lf%lf",&x[i],&y[i],&l); fo(i,1,n) scanf("%lf%lf%lf",&a[i],&b[i],&r); fo(i,1,m) fo(j,1,m) f[i][j]=inf; fo(i,1,m) fo(j,1,m) { bool flag=1; fo(k,1,n) { double x1=a[k]-x[i],y1=b[k]-y[i]; double x2=a[k]-x[j],y2=b[k]-y[j]; double tmp=x1*y2-x2*y1; //叉积 if(tmp>=eps) {flag=0;break;} if(tmp>-eps && tmp<eps && x1*x2+y1*y2>=eps) {flag=0;break;} } if(flag) f[i][j]=1; } printf("%d\n",floyd()); return 0; }