Eva

Time Limit: 4 Sec  Memory Limit: 162 MB
Submit: 5066  Solved: 1619
Description

　　某公司加工一种由铁、铝、锡组成的合金。他们的工作很简单。首先进口一些铁铝锡合金原材料，不同种类的
原材料中铁铝锡的比重不同。然后，将每种原材料取出一定量，经过融解、混合，得到新的合金。新的合金的铁铝
锡比重为用户所需要的比重。 现在，用户给出了n种他们需要的合金，以及每种合金中铁铝锡的比重。公司希望能
够订购最少种类的原材料，并且使用这些原材料可以加工出用户需要的所有种类的合金。

　　第一行两个整数m和n（m, n ≤ 500），分别表示原材料种数和用户需要的合金种数。第2到m + 1行，每行三
个实数a, b, c（a, b, c ≥ 0 且 a + b + c = 1），分别表示铁铝锡在一种原材料中所占的比重。第m + 2到m +
n + 1行，每行三个实数a, b, c（a, b, c ≥ 0 且 a + b + c = 1），分别表示铁铝锡在一种用户需要的合金中
所占的比重。

　　一个整数，表示最少需要的原材料种数。若无解，则输出–1。 

10 10
0.1 0.2 0.7
0.2 0.3 0.5
0.3 0.4 0.3
0.4 0.5 0.1
0.5 0.1 0.4
0.6 0.2 0.2
0.7 0.3 0
0.8 0.1 0.1
0.9 0.1 0
1 0 0
0.1 0.2 0.7
0.2 0.3 0.5
0.3 0.4 0.3
0.4 0.5 0.1
0.5 0.1 0.4
0.6 0.2 0.2
0.7 0.3 0
0.8 0.1 0.1
0.9 0.1 0
1 0 0

5

/**************************************************************

    Problem: 1027

    User: ictsing

    Language: C++

    Result: Accepted

    Time:1328 ms

    Memory:2320 kb

****************************************************************/

 

//1027: [JSOI2007]合金

//m种原材料，n种需要的合金，每种合金和原材料中铁铝锡都有一定的比重

//求最少需要几种合金能够加工出所有种类的合金

/*

神题，首先已知前两个的比重可以推出后面的那个的比重。

所以我们只需要前两个元素就可以了。

常见的思路把前两个元素看作该点的坐标，这样可以得到一个图。

一个新的产品能够被合成出来就需要，这个产品在某两个产品相连的线段上。

这里的dis怎么设置呢，就是如果这个点在这个线段上dis[j][k]=1,否则dis[j][k]=inf;

问题转化为求一个点数最少的多边形包围n个点

枚举向量a[j]-a[i]，判断其他点是否在它的同一边

c>eps || fabs(c)<eps && Dot(b[k],a[i],a[j])>eps

枚举都是一样的，可以自己判断

然后floyd求最小环即可

特判掉n个点共点，以及某个点n在某个向量所在的直线上但不在线段上

特判是失分的细节问题

*/

#include <iostream>

#include <cstdio>

using namespace std;

inline int read()

{

  int num=0,flag=1;

  char ch;

  do{

    ch=getchar();

    if(ch=='-') flag=-1;

  }while(ch<'0'||ch>'9');

  do{

    num=num*10+ch-'0';

    ch=getchar();

  }while(ch>='0'&&ch<='9');

  return num*flag;

}

const int mt = 500+5;

const int inf = 0x3f3f3f3f;

const double eps=1e-8;

struct point

{

    double x,y;

}a[mt<<1],b[mt<<1];

double cross(point a,point b,point c)

{

    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);

}

double dot(point a,point b,point c)

{//b-a c-a

    return (b.x-a.x)*(c.x-a.x)+(b.y-a.y)*(c.y-a.y);

}

int dis[mt][mt];

double abs(double x)

{

    if(x>0) return x;

    return -x;

}

int main()

{

    int m=read(),n=read();double x;

    for(int i=1;i<=m;i++)

        scanf("%lf%lf%lf",&a[i].x,&a[i].y,&x);

    for(int i=1;i<=n;i++)

        scanf("%lf%lf%lf",&b[i].x,&b[i].y,&x);

    for(int i=1;i<=m;i++)

        for(int j=1;j<=m;j++)

        {

            dis[i][j]=inf;

            bool flag=true;

            for(int k=1;k<=n;k++)

            {

                double tmp=cross(b[k],a[i],a[j]);

                if(tmp>eps||(abs(tmp)<eps&&dot(b[k],a[i],a[j])>eps)) 

                {flag=false;break;}

            }

            if(flag) dis[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++)

               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]);

    if(ans==inf) {puts("-1");return 0;}

    printf("%d\n",ans);

    return 0;

}