合金

标志： metal.*

试题描述：

某公司加工一种由铁、铝、锡组成的合金。他们的工作很简单。首先进口一些铁铝锡合金原材料，不同种类的原材料中铁铝锡的比重不同。然后，将每种原材料取出一定量，经过融解、混合，得到新的合金。新的合金的铁铝锡比重为用户所需要的比重。

现在，用户给出了 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 。

输入样例：

3 2

0.25 0.25 0.5

0 0.5 0.5

1 0 0

0.7 0.1 0.2

0.85 0.05 0.1

 

输出样例：

2

   这道题是一个很难的问题。

   首先不难看出，合金的三种成分中只有两种成分的数据是有用的，因为第 3 种成分的比例可以由前两种成分的比例推出。因此，对于每一种合金，都可以用唯一的有序实数对 (x, y) 来进行表示。

  那么，给出的若干合金可以表示成为二维平面上的若干点，那么，这些合金可以合成的合金的范围应该是什么呢？

  试考虑将任意两种合金 (x1, y1), (x2, y2) 等比例进行混合，则新合金在平面上的坐标应该表示为：（（x1+x2）/2,(y1+y2)/2） ，也就是这两点连线上的中点。

  换句话说，如果平面内任意两个给定的点所代表的合金都可以得到，则这两点连线的中点所代表的合金也可以得到。熟悉凸包的选手一下子就可以想到，敢于凸包凸性的定义中最为简洁的一条是：对于任意(x1,y1),(x2,y2)属于D有 （（x1+x2）/2,(y1+y2)/2）D 。因此，用平面上若干点所代表的合金，能且仅能合成这若干点构成的凸包内的所有点所代表的合金。

  由此，本题就变成了如下的题目：设提供的合金点集为 A ，用户定制的合金点集为 B ，从 A 中选取最少的点，使得 B 中所有点都在 A 中选取点的凸包内。（也可以认为，从 A 中选取的所有点必须构成凸多边形）。

  这并不是一个很容易解决的问题。

 

  既然不能一下子解决，我们先来看几种特殊情况。（设选取的点数为 k ）

1、 无解。求取 A 点集的凸包，判断 B 中是否所有点都在凸包内。

2、 K=1: 只有一种情况： B 点集内只有一个点（或多个重点），且 A 点集中恰有这个点。

3、 K=2: B 点集所有点共线，且 A 点集中存在两个点，满足这两个点与 B 点集中所有点共线，同时 B 点集中所有点都落在这两个点所连接形成的线段上。

4、 K=3: 这时就没有前两种情况那么简单了。我们考虑使用穷举法解题。当然，如果枚举三角形的三个顶点的话，是超时的，因为验证还需要线形的时间。但实际上，深入思考的话，我们发现只需要枚举三角形的底边就可以了。

设底边为 CD ，则如果以 CD 为底边的三角形满足题意的话，必然有：

(1) 、 B 点集中所有点均位于 CD 边的同侧。

(2) 、如右图。当且仅当在 A 区域中存在 A 点集中的点，此时的三角形覆盖才是可行的。

5 、 K=4: 同 K=3 时一样处理。此时必然构成一个 四边形。我们枚举四边形的对角线，然后对两侧模仿 k=3 的情形如法炮制。时间复杂度仍然为 O(n³) （较松）

 

以上我们讨论了无解和 k<=4 的所有情况，事实上，如果对于这些情况全都不符合的数据输出 5 的话，则这样的程序可以拿到满分，因为本题的数据的答案都不超过 5 （好弱的数据！！！）但是，本题事实上还有不骗分的算法——甚至比分类讨论的算法时间都要少。

 

试考虑将 A 点集中的所有点看作一个图的顶点，则“选取点”的工作可以看作是图中的一个回路。这个回路应该满足下列性质：

1、 B 点集中所有点必须在回路中任意一条边的同侧。

2、 设 B 点集中任意一点 (xx, yy) ，则回路中所有边对该点形成的圆心角的度数之和应该为 2pi. （或者说，至少为 2pi ，因为绕圈也是允许的）。（如右图）

3、 回路上的顶点数应尽可能的少。

根据这几条性质，我们可以构造一个图 G ：

1、 如果 B 点集中所有点并不在某条边的同侧，则删去这条边。

2、 否则，边权等于这条边所对应的圆心角的角度。注意：角度是有符号的，且 v(k1, k2) = -v(k2, k1) ，而角度的符号可以这样定义：如果中心点 O 在向量 v(k1, k2) 的右手螺旋方向，则向量 v(k1, k2) 所成的圆心角是正的，否则是负的。

 

  然后我们考虑算法。注意到这并不是一个经典的最短路径问题，而是一个在权值和不小于给定值的条件下求最少顶点的路径。由于本题中构作图的特殊性质，可以用一种迭代的方法进行：每次枚举一步，然后判断这一步之后各点的权值和情况，取最大值即可。由于本题中图的特殊性，所以这样得出来的解肯定是满足题意的。

  用这种算法作为主题，再加上前面讨论过的 k=1, k=2 和无解这三种特殊情况的判断，就可以完美的解决问题了。（当然，无解情形可以用迭代 n+1 次但还未找到解的情况代替，但这样做很慢，而且无法通过给定的数据）