某公司加工一种由铁、铝、锡组成的合金。他们的工作很简单。首先进口一些铁铝锡合金原材料，不同种类的 原材料中铁铝锡的比重不同。然后，将每种原材料取出一定量，经过融解、混合，得到新的合金。新的合金的铁铝 锡比重为用户所需要的比重。 现在，用户给出了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。
思路：对于每种原料(a , b , c),因为有a + b + c = 1,所以知道了a、b之后c就知道了，所以用一个二维的（a, b）就可以表示一种原料，而这也就对应了二维平面上的一个点。同理，每一种待合成材料也可以用一个二维平面上的点来表示。
那么，原料(x1 , y1)和原料(x2 , y2)可以合成的合金有哪些呢？这两者合成的合金对应的点如果是（x,y），那么有x = k * x1 + (1 - k) * x2 , y = k * y1 + (1 - k) * y2,直线的两点式为(x - x1) / (x2 - x1) = (y - y1) / (y2 - y1)，我们发现（x，y）满足直线的两点式，所以（x，y）在过(x1 , y1),(x2 , y2)的直线上，又因为0<= k <= 1，所以（x，y）在以(x1 , y1)(x2 , y2)为端点的线段上。
如果平面上代表原料的某些点构成了一个凸多边形，那么有这个凸多边形内部的每一个点代表的合金，都可以由构成凸多边形的原料来合成。怎么说明呢？首先，我们可以知道凸多边形的边上的每一点都可以合成（上一段已经说明），那么，对于凸多边形内部的任一点K，过它做一条直线，可以交凸多边形于两点P、Q，因为这两点P、Q都可以合成得到，所以K可以通过合成P、Q合成得到，所以K可以合成，所以凸多边形内部任一点都可以合成得到。
所以问题就变成了这样，给定点集S1、S2，要求在S1中找一个点数最少的点集S‘，使得S’构成凸包可以包含S2的所有的点。
对于这个问题，可以看成求最小环。我们这样建图：对于任意两点A、B，如果待合成的所有合金对应的点全部在直线AB的右边，或者在线段AB（注意是线段）上，那么，就建一条从点A到点B的有向边，然后在图上跑一次floyd求出最小环。注意这样求出的环的最小长度为2，但是有一种特殊情况，就是所有待合成合金重合于一点，然后这一点在原材料中就存在，那么在这种情况下答案就是1。
#pragma warning(disable:4786) #pragma comment(linker, "/STACK:102400000,102400000") #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<vector> #include<cmath> #include<string> #include<sstream> #include<bitset> #define LL long long #define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;++i) #define mem(a,x) memset(a,x,sizeof(a)) #define lson l,m,x<<1 #define rson m+1,r,x<<1|1 using namespace std; const int INF = 99999; const int mod = 1e9 + 7; const double PI = acos(-1.0); const double eps=1e-10; const int maxn = 500 + 5; int dist[maxn][maxn] , mp[maxn][maxn]; int n , m , minloop; int dcmp(double x) { if(fabs(x) < eps) return 0; else return x > 0 ? 1 : -1; } struct Vector { double x , y; Vector(double _x = 0 , double _y = 0) :x(_x),y(_y){}; }need[maxn] , has[maxn]; double Cross(const Vector & a , const Vector & b) { return a.x * b.y - a.y * b.x; } double Dot(const Vector & a , const Vector & b) { return a.x * b.x + a.y * b.y; } bool OnSegment(Vector p , Vector a1 , Vector a2) { Vector v1 = Vector(a1.x - p.x , a1.y - p.y) , v2 = Vector(a2.x - p.x , a2.y - p.y); return dcmp(Cross(v1 , v2)) == 0 && dcmp(Dot(v1 , v2)) <= 0; } void create_edge(int x , int y) { Vector v1 = Vector(has[y].x - has[x].x , has[y].y - has[x].y) , v2; for(int i = 1 ; i <= n ; i++){ v2 = Vector(need[i].x - has[x].x , need[i].y - has[x].y); int t = dcmp(Cross(v1 , v2)); if(t < 0) return ; if(t == 0 && !OnSegment(need[i] , has[x] , has[y])) return ; } mp[x][y] = dist[x][y] = 1; } void Floyd() //有向图求最小环，其实就是做一次Floyd，然后找最小的dist[i][i] { minloop = INF; for(int k = 1 ; k <= m ; k++){ for(int i = 1 ; i <= m ; i++){ for(int j = 1 ; j <=m ; j++){ if(dist[i][j] > dist[i][k] + dist[k][j]){ dist[i][j] = dist[i][k] + dist[k][j]; } } } } for(int i = 1 ; i <= m ; i++){ minloop = min(minloop , dist[i][i]); } } int spj() { int ret , flag = 1; for(int i = 2 ; i <= n ; i++){ if(need[i].x != need[i - 1].x || need[i].y != need[i - 1].y){ flag = 0; break; } } if(!flag) return 0; for(int i = 1 ; i <= m ; i++){ if(has[i].x == need[1].x && has[i].y == need[1].y){ puts("1"); return 1; } } return 0; } int main() { while(scanf("%d %d" , &m , &n) != EOF){ double cc ; for(int i = 1 ; i <= m ; i++){ scanf("%lf %lf %lf" , &has[i].x , &has[i].y , &cc); } for(int i = 1 ; i <= n ; i++){ scanf("%lf %lf %lf" , &need[i].x , &need[i].y , &cc); } if(spj()) continue; for(int i = 1 ; i <= m ; i++){ for(int j = 1 ; j <= m ; j++){ mp[i][j] = dist[i][j] = INF; } } for(int i = 1 ; i <= m ;i++){ for(int j = 1 ; j <= m ; j++){ if(i != j) create_edge(i , j); } } Floyd(); if(minloop < INF) printf("%d\n" , minloop); else printf("-1\n"); } return 0; }