?????????????? 合金

標志： metal.*

試題描述：

某公司加工一種由鐵、鋁、錫組成的合金。他們的工作很簡單。首先進口一些鐵鋁錫合金原材料，不同種類的原材料中鐵鋁錫的比重不同。然后，將每種原材料取出一定量，經(jīng)過融解、混合，得到新的合金。新的合金的鐵鋁錫比重為用戶所需要的比重。

現(xiàn)在，用戶給出了 n 種他們需要的合金，以及每種合金中鐵鋁錫的比重。公司希望能夠訂購最少種類的原材料，并且是用這些原材料可以加工出用戶需要的所有種類的合金。

?

輸入文件的第一行是兩個整數(shù) m 和 n ， (m, n <= 500) ，分別表示原材料種數(shù)和用戶需要的合金種數(shù)。

第 2 到 m+1 行，每行三個實數(shù) a, b, c, (a, b, c >= 0 且 a+b+c = 1) ，分別表示鐵鋁錫在一種原材料中所占的比重。

第 m+2 到 m+n+1 行，每行三個實數(shù) a, b, c, (a, b, c >= 0 且 a+b+c = 1) ，分別表示鐵鋁錫在一種用戶需要的合金中所占的比重。

輸出一個整數(shù)，表示最少需要的原材料種數(shù)。若無解，則輸出 -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

?? 這道題是一個很難的問題。

?? 首先不難看出，合金的三種成分中只有兩種成分的數(shù)據(jù)是有用的，因為第 3 種成分的比例可以由前兩種成分的比例推出。因此，對于每一種合金，都可以用唯一的有序?qū)崝?shù)對 (x, y) 來進行表示。

? 那么，給出的若干合金可以表示成為二維平面上的若干點，那么，這些合金可以合成的合金的范圍應(yīng)該是什么呢？

? 試考慮將任意兩種合金 (x1, y1), (x2, y2) 等比例進行混合，則新合金在平面上的坐標應(yīng)該表示為：（（x1+x2）/2,(y1+y2)/2） ，也就是這兩點連線上的中點。

? 換句話說，如果平面內(nèi)任意兩個給定的點所代表的合金都可以得到，則這兩點連線的中點所代表的合金也可以得到。熟悉凸包的選手一下子就可以想到，敢于凸包凸性的定義中最為簡潔的一條是：對于任意(x1,y1),(x2,y2)屬于D有 （（x1+x2）/2,(y1+y2)/2）D 。因此，用平面上若干點所代表的合金，能且僅能合成這若干點構(gòu)成的凸包內(nèi)的所有點所代表的合金。

? 由此，本題就變成了如下的題目：設(shè)提供的合金點集為 A ，用戶定制的合金點集為 B ，從 A 中選取最少的點，使得 B 中所有點都在 A 中選取點的凸包內(nèi)。（也可以認為，從 A 中選取的所有點必須構(gòu)成凸多邊形）。

? 這并不是一個很容易解決的問題。

?

? 既然不能一下子解決，我們先來看幾種特殊情況。（設(shè)選取的點數(shù)為 k ）

1、 無解。求取 A 點集的凸包，判斷 B 中是否所有點都在凸包內(nèi)。

2、 K=1: 只有一種情況： B 點集內(nèi)只有一個點（或多個重點），且 A 點集中恰有這個點。

3、 K=2: B 點集所有點共線，且 A 點集中存在兩個點，滿足這兩個點與 B 點集中所有點共線，同時 B 點集中所有點都落在這兩個點所連接形成的線段上。

4、 K=3: 這時就沒有前兩種情況那么簡單了。我們考慮使用窮舉法解題。當然，如果枚舉三角形的三個頂點的話，是超時的，因為驗證還需要線形的時間。但實際上，深入思考的話，我們發(fā)現(xiàn)只需要枚舉三角形的底邊就可以了。

設(shè)底邊為 CD ，則如果以 CD 為底邊的三角形滿足題意的話，必然有：

(1) 、 B 點集中所有點均位于 CD 邊的同側(cè)。

(2) 、如右圖。當且僅當在 A 區(qū)域中存在 A 點集中的點，此時的三角形覆蓋才是可行的。

5 、 K=4: 同 K=3 時一樣處理。此時必然構(gòu)成一個 四邊形。我們枚舉四邊形的對角線，然后對兩側(cè)模仿 k=3 的情形如法炮制。時間復(fù)雜度仍然為 O(n³) （較松）

?

以上我們討論了無解和 k<=4 的所有情況，事實上，如果對于這些情況全都不符合的數(shù)據(jù)輸出 5 的話，則這樣的程序可以拿到滿分，因為本題的數(shù)據(jù)的答案都不超過 5 （好弱的數(shù)據(jù)！！！）但是，本題事實上還有不騙分的算法——甚至比分類討論的算法時間都要少。

?

試考慮將 A 點集中的所有點看作一個圖的頂點，則“選取點”的工作可以看作是圖中的一個回路。這個回路應(yīng)該滿足下列性質(zhì)：

1、 B 點集中所有點必須在回路中任意一條邊的同側(cè)。

2、 設(shè) B 點集中任意一點 (xx, yy) ，則回路中所有邊對該點形成的圓心角的度數(shù)之和應(yīng)該為 2pi. （或者說，至少為 2pi ，因為繞圈也是允許的）。（如右圖）

3、 回路上的頂點數(shù)應(yīng)盡可能的少。

根據(jù)這幾條性質(zhì)，我們可以構(gòu)造一個圖 G ：

1、 如果 B 點集中所有點并不在某條邊的同側(cè)，則刪去這條邊。

2、 否則，邊權(quán)等于這條邊所對應(yīng)的圓心角的角度。注意：角度是有符號的，且 v(k1, k2) = -v(k2, k1) ，而角度的符號可以這樣定義：如果中心點 O 在向量 v(k1, k2) 的右手螺旋方向，則向量 v(k1, k2) 所成的圓心角是正的，否則是負的。

?

? 然后我們考慮算法。注意到這并不是一個經(jīng)典的最短路徑問題，而是一個在權(quán)值和不小于給定值的條件下求最少頂點的路徑。由于本題中構(gòu)作圖的特殊性質(zhì)，可以用一種迭代的方法進行：每次枚舉一步，然后判斷這一步之后各點的權(quán)值和情況，取最大值即可。由于本題中圖的特殊性，所以這樣得出來的解肯定是滿足題意的。

? 用這種算法作為主題，再加上前面討論過的 k=1, k=2 和無解這三種特殊情況的判斷，就可以完美的解決問題了。（當然，無解情形可以用迭代 n+1 次但還未找到解的情況代替，但這樣做很慢，而且無法通過給定的數(shù)據(jù)）