Description
某公司加工一种由铁、铝、锡组成的合金。他们的工作很简单。首先进口一些铁铝锡合金原材料，不同种类的原材料中铁铝锡的比重不同。然后，将每种原材料取出一定量，经过融解、混合，得到新的合金。新的合金的铁铝锡比重为用户所需要的比重。
现在，用户给出了n种他们需要的合金，以及每种合金中铁铝锡的比重。公司希望能够订购最少种类的原材料，并且使用这些原材料可以加工出用户需要的所有种类的合金。
Input
第一行两个整数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），分别表示铁铝锡在一种用户需要的合金中所占的比重。
Output
一个整数，表示最少需要的原材料种数。若无解，则输出–1。
Sample
Input
3 2
0.25 0.25 0.5
0 0.6 0.5
1 0 0
0.7 0.1 0.2
0.85 0.05
0.1
Sample Output
2
看到这题首先想到向量
虽然它有三维，但是有一维是不需要的（前两维都对了，第三维肯定也对了）
所以我们可以把它们都看成平面上的点
观察和分析后，发现两种合金合成另一种合金的条件是，第三种合金的点在前两种合金的点的连线段上
所以我们选定一些点作为原料，那么在这些点构成的凸包内部的点都能合成
所以我们要选最少的点，使得目标点都在这些点所构成的凸包内
相当于我们要选最少的边，把目标点围起来
枚举两个点，如果目标点都在左边或在线段上，距离就为1，否则距离为inf，这个用叉积判断
然后用floyd求最小环就行了
floyd最小环是不能解决1或2的，所以要打一个特判ans=1或2的
1 const 2 maxn=505; 3 inf=1000000; 4 eps=1e-7; 5 type 6 node=record 7 x,y:double; 8 end; 9 var 10 n,m,ans:longint; 11 a,b:array[0..maxn]of node; 12 f,g:array[0..maxn,0..maxn]of longint; 13 flag:array[0..maxn]of boolean; 14 15 function cj(x1,y1,x2,y2:double):double; 16 begin 17 exit(x1*y2-y1*x2); 18 end; 19 20 procedure init; 21 var 22 i,j,k,num:longint; 23 s:double; 24 begin 25 ans:=inf; 26 read(n,m); 27 fillchar(f,sizeof(f),1); 28 fillchar(g,sizeof(g),1); 29 for i:=1 to n do 30 read(a[i].x,a[i].x,a[i].y); 31 for i:=1 to m do 32 read(b[i].x,b[i].x,b[i].y); 33 for i:=1 to n do 34 begin 35 j:=0; 36 for k:=1 to m do 37 if (abs(a[i].x-b[k].x)>eps) or (abs(a[i].y-b[k].y)>eps) then 38 begin 39 j:=1; 40 break; 41 end; 42 if j=0 then 43 begin 44 write(1); 45 halt; 46 end; 47 end; 48 for i:=1 to n do 49 for j:=1 to n do 50 if i<>j then 51 begin 52 g[i,j]:=1; 53 f[i,j]:=1; 54 num:=0; 55 for k:=1 to m do 56 begin 57 s:=cj(a[j].x-a[i].x,a[j].y-a[i].y,b[k].x-a[i].x,b[k].y-a[i].y); 58 if (abs(s)<eps) and ((b[k].x-a[i].x)*(b[k].x-a[j].x)<0) then inc(num); 59 if s>eps then 60 begin 61 g[i,j]:=inf; 62 f[i,j]:=inf; 63 break; 64 end; 65 end; 66 if num=m then 67 begin 68 write(2); 69 halt; 70 end; 71 end; 72 for i:=1 to n do 73 for j:=1 to n do 74 if f[i,j]<inf then flag[i]:=true; 75 end; 76 77 function min(x,y:longint):longint; 78 begin 79 if x<y then exit(x); 80 exit(y); 81 end; 82 83 procedure work; 84 var 85 i,j,k:longint; 86 begin 87 for k:=1 to n do 88 if flag[k] then 89 begin 90 for i:=1 to k-1 do 91 if flag[i] then 92 for j:=1 to i-1 do 93 if flag[j] then 94 ans:=min(ans,min(f[i,j]+g[j,k]+g[k,i],f[j,i]+g[i,k]+g[k,j])); 95 for i:=1 to n do 96 if flag[i] then 97 for j:=1 to n do 98 if flag[j] then 99 f[i,j]:=min(f[i,j],f[i,k]+f[k,j]); 100 end; 101 if ans=inf then write(-1) 102 else write(ans); 103 end; 104 105 begin 106 init; 107 work; 108 end.