题目：
http://www.lydsy.com/JudgeOnline/problem.php?id=1027显然对于每种金属，我们只用存任意两个量，因为第三个可以用1减去存下来的两个得到。
把这些二元组作为坐标映射到坐标系上。
如果有解，则所有需要的材料必在原材料所组成的一个凸包中。
对于任意两个原材料，若所有需要的材料都在连边同一侧或边上，则将两点间连一条长度为1的边，这样问题就转化为最小环，用floyd求即可。
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <ctime>
using namespace std;
const int MaxN=501;
const int oo=100000001;
const double e=1e-10;
struct point
{
double x,y;
};
point operator -(point a,point b)
{
point c;
c.x=a.x-b.x;
c.y=a.y-b.y;
return c;
}
bool operator ==(point a,point b)
{
return a.x==b.x && a.y==b.y;
}
int n,m;
point a[MaxN],b[MaxN];
int c[MaxN][MaxN],d[MaxN][MaxN];
double det(point a,point b)
{
return (a.x*b.y-a.y*b.x);
}
int pd(point a,point b,point c)
{
double k=det(b-a,c-a);
if (k>=-e && k<=e) return 0;
if (k>0) return 1;
if (k<0) return -1;
}
void init()
{
cin>>n>>m;
for (int i=0;i<n;i++)
{
double z;
cin>>a[i].x>>a[i].y>>z;
}
for (int i=0;i<m;i++)
{
double z;
cin>>b[i].x>>b[i].y>>z;
}
}
int treat()
{
for (int i=0;i<n;i++)
{
bool f=1;
for (int j=0;j<m;j++)
{
if (a[i].x*b[j].y!=a[i].y*b[j].x || a[i].y*(1-b[j].x-b[j].y)!=(1-a[i].x-a[i].y)*b[j].y || a[i].x*(1-b[j].x-b[j].y)!=(1-a[i].x-a[i].y)*b[j].x)
{
f=0;
break;
}
}
if (f==1)
{
return 1;
}
}
for (int i=0;i<n;i++)
{
for (int j=0;j<n;j++)
{
if (i==j)
{
continue;
}
if (a[i]==a[j])
{
c[i][j]=oo;
continue;
}
bool f=1;
int k;
for (k=0;pd(a[i],a[j],b[k])==0 && k<m && b[k].x<=max(a[i].x,a[j].x) && b[k].x>=min(a[i].x,a[j].x);k++);
if (k==m)
{
return 2;
}
for (int k=0;k<m;k++)
{
if (pd(a[i],a[j],b[k])<0)
{
f=0;
break;
}
}
if (f==1)
{
c[i][j]=1;
}
else
{
c[i][j]=oo;
}
}
}
return 0;
}
int floyd()
{
int ans=oo;
memcpy(d,c,sizeof(d));
for (int k=0;k<n;k++)
{
for (int i=0;i<n;i++)
if (i!=k)
for (int j=0;j<n;j++)
{
if (j!=k && j!=i)
ans=min(ans,d[i][j]+c[k][i]+c[j][k]);
}
for (int i=0;i<n;i++)
for (int j=0;j<n;j++)
{
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
}
return ans;
}
int main()
{
init();
int f=treat();
if (f!=0)
{
cout<<f<<endl;
}
else
{
int ans=floyd();
if (ans==oo)
{
cout<<-1<<endl;
}
else
{
cout<<ans<<endl;
}
}
return 0;
}