1、Two Dimenal Convex Hull二維凸包譯 by FeliCrazy(MSN felic)準(zhǔn)備知識(shí)幾何學(xué)數(shù)學(xué)模型給出平面內(nèi)的點(diǎn)集，找出面積最小的凸多邊形，使得這些點(diǎn)在這個(gè)多邊形之內(nèi)（或者在它的邊上）?？梢钥闯觯噙呅蔚捻旤c(diǎn)必須是給定點(diǎn)集中的點(diǎn)。例題：放牧奶牛農(nóng)夫想要修建一個(gè)柵欄，來(lái)防止討厭的當(dāng)?shù)卮髮W(xué)生在他的奶牛們睡覺的時(shí)候把它們掀翻。他的每頭奶牛都有一個(gè)最喜歡的吃草點(diǎn)，農(nóng)夫想要把這些點(diǎn)都圍在柵欄內(nèi)。農(nóng)夫要圍出一個(gè)凸的形狀，因?yàn)檫@樣更容易把奶牛趕進(jìn)牧場(chǎng)。幫助農(nóng)夫確定面積最小的而且包括所牛喜愛的吃草點(diǎn)的柵欄形狀。算法解決二維凸包問(wèn)題有好幾種算法。這里，只介紹比較容易編碼和的“卷”算法

2、（其實(shí)就是所說(shuō)的漢掃描法譯者注）。算法的基本是在一個(gè)肯定會(huì)在凸包內(nèi)的點(diǎn)周圍不斷地由順時(shí)針或逆時(shí)針?lè)较蛟黾禹旤c(diǎn)，并確保每個(gè)內(nèi)角都小于 180 度（保證最終是凸的）。如果三個(gè)連續(xù)的頂點(diǎn)的角度大于 180 度，刪掉中間的點(diǎn)。可以用兩個(gè)沿著多邊形邊的連續(xù)向量的叉積來(lái)判斷角度是否大于 180 度。凸包算法流程：找出一個(gè)必定會(huì)在凸包內(nèi)的中點(diǎn)計(jì)算每個(gè)點(diǎn)和中點(diǎn)的連線與 x 軸的夾角（在 0360 度的范圍內(nèi)）根據(jù)這些夾角對(duì)頂點(diǎn)排序加入最初的兩個(gè)頂點(diǎn)對(duì)于除最后一個(gè)頂點(diǎn)以外的其余頂點(diǎn)讓其成為凸包上的下一個(gè)頂點(diǎn)檢查它和前面兩個(gè)頂點(diǎn)組成的角是否大于 180 度如果它和前面兩個(gè)頂點(diǎn)組成的角大于 180 度，那么把它前面

3、那個(gè)頂點(diǎn)刪掉 加入最后一個(gè)頂點(diǎn)完成上述的刪除任務(wù)檢查最后一個(gè)頂點(diǎn)和它的前一個(gè)頂點(diǎn)和第一個(gè)頂點(diǎn)所組成的角是否大于 180 度，或者最后一個(gè)頂點(diǎn)和第一、第二個(gè)頂點(diǎn)組成的角是否大于 180 度。如果第一種情況為真，刪除最后一個(gè)頂點(diǎn)，并且檢查倒數(shù)第二個(gè)頂點(diǎn)。如果第二種情況為真，刪除第一個(gè)頂點(diǎn)，繼續(xù)檢查。當(dāng)兩種情況都不為真時(shí)，停止。由于角度的計(jì)算方式，增加頂點(diǎn)的時(shí)間復(fù)雜度是線性的（就是所說(shuō)的O(n) ）。因此，運(yùn)行的時(shí)間復(fù)雜度決定于排序的時(shí)間復(fù)雜度，所以“卷法”的時(shí)間復(fù)雜度是 O( n log n)，這是最優(yōu)的。偽代碼這里是凸包算法的偽代碼：# # # # # # # # 123x(i), y(i) i

4、s the x,y of the i-th po zcrossprod(v1,v2) - z of the vectors v1, v2 if zcrossprod(v1,v2) itioncomponent0,then v2 is right of v1since we add counter-clockwise angle 180 deg(midx, midy) For all po (midx, midy)=s=(0, 0)i (midx,midy) + s)(x(i)/npos, 4 For all poy(i)/npo s i5 angle(i) = atan2(y(i) x(i)

5、- midx)- midy,6perm(i) = i7 #sort perm based on the angle() i.e., angle(perm(0) 11)and-2)zcrossprod(hull(hull-13 hull(hull-1),hull(hull-1) - p) 11)and-2)zcrossprod(hull(hull-19 hull(hull-1),hull(hull-1) - p)=2 andzcrossprod(p25 hull(hull-1),hull(hullstart) -p) =2 andzcrossprod(hull(hullstart) hull(h

6、ullstart+1) - hull(hullstart) 0)- p,3031323334hullstart = hullstart + flag = truewhile flag hull(hull) = p1hull= hull+ 1對(duì)于下面的，使用這些頂點(diǎn)：選擇一個(gè)中算夾角，并排序。現(xiàn)在，從加入最初的兩個(gè)頂點(diǎn)開始。現(xiàn)在，加入第三個(gè)頂點(diǎn)。由于這步操作沒有和前兩個(gè)頂點(diǎn)一個(gè)大于 180 度的角，只需加入這個(gè)頂點(diǎn)。加入第四個(gè)頂點(diǎn)。這一次沒有大于 180 度的角，所以不必做的工作。加入第五個(gè)頂點(diǎn)。由于第三個(gè)，第四個(gè)，和第五個(gè)頂點(diǎn)了一個(gè)大于 180 度的角（一個(gè)“向右的”轉(zhuǎn)彎），刪去第四個(gè)頂點(diǎn)。第

7、二個(gè)，第三個(gè)，和第四個(gè)頂點(diǎn)沒有了加入第五個(gè)頂點(diǎn)的任務(wù)。一個(gè)大于 180 度的角，所以完成加入第六個(gè)，第七個(gè)，和第八 8 個(gè)頂點(diǎn)。這個(gè)過(guò)程中沒有附加的工作。接著，加入最后一個(gè)頂點(diǎn)。第八個(gè)，第九個(gè)，和第一個(gè)頂點(diǎn)“右轉(zhuǎn)”；刪除第九個(gè)頂點(diǎn)。第七個(gè)，第八個(gè)，和第一個(gè)頂點(diǎn)已經(jīng)完成了，第八個(gè)，第一個(gè)，和第二個(gè)頂點(diǎn)“右轉(zhuǎn)”，所以須刪除第一個(gè)頂點(diǎn)?，F(xiàn)在，第八個(gè)，第二個(gè)，和第三個(gè)頂點(diǎn)“右轉(zhuǎn)”，所以頂點(diǎn)。又要?jiǎng)h除第二個(gè)剩下的頂點(diǎn)并不頂點(diǎn)的凸包?！白筠D(zhuǎn)”原則，所以已經(jīng)完成了任務(wù)，并且建立了給出問(wèn)題提示類似把頂點(diǎn)放入多邊形的題目通常是求凸包。如果題目要求一個(gè)面積最小的凸多邊形，或者周長(zhǎng)最小的凸多邊形，那么幾乎可以確定是

8、要求凸包了。推廣不幸的是，這個(gè)算法不能簡(jiǎn)單地推廣到三維的情形。幸運(yùn)的是，三維凸包算法全都超級(jí)復(fù)雜（以上的更），所以題目不太可能要你去求。如果你給多邊形加上任何限制條件時(shí)，這個(gè)算法就玩完了（例如，多邊形的頂點(diǎn)不多于 n 個(gè)，或者必須是矩形）。例題樹的難題 IOI 1991, problem 2已知：有一些樹，你必須用鐵絲圍繞這些樹，使得你用的鐵絲最短。計(jì)算哪些樹會(huì)在多邊形的頂點(diǎn)上和鐵絲的長(zhǎng)度，還有農(nóng)夫的小屋是在多邊形內(nèi)，還是在它之外，還是跨過(guò)多邊形的邊？分析：多邊形的頂點(diǎn)和鐵絲的長(zhǎng)度可以由問(wèn)題直接得到。農(nóng)夫的小屋是坐標(biāo)軸上的一個(gè)矩形，你需要一點(diǎn)幾何學(xué)知識(shí)來(lái)確定矩形中的所有點(diǎn)都在凸包中，或者都在凸包外，或者一些在凸包內(nèi)，一些在凸包外。這樣你就可以得到你想要的查查幾何手冊(cè)，找一下這類問(wèn)題的解法。的護(hù)城河建設(shè)已知：一些多邊形房屋，計(jì)算包含這些多邊形除去一個(gè)多邊形的護(hù)城河的最小長(zhǎng)度。分析：計(jì)算