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

標(biāo)志： metal.*

試題描述：

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

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

?

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

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

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

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

?? 這道題是一個(gè)很難的問(wèn)題。

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

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

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

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

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

? 這并不是一個(gè)很容易解決的問(wèn)題。

?

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

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

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

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

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

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

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

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

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

?

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

?

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

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

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

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

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

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

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

?

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

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