題目簡述：

??? 給出一個平面點集S，求一個面積最小的矩形使其包含S所有的點。

預備知識：

?? ?在求解這道題之前我們先要了解一些關于凸包的知識。

?? ?什么是凸包？簡單地說，對于一個平面點集S，我們把完全包含該點集的最小的凸多邊形叫做點集S的凸包H。

?? ?凸包一個很重要的性質就是它“凸”的性質。這個性質對我們理解和計算凸包都有很大的幫助。

I）?????????????? 對點集S中任意一點a，當且僅當存在直線p過a點并使得S中除a外所有點均在p的一側，則a為凸包上的一頂點。

II）??????????? 對點集S中任意兩點a,b，當且僅當S中除a,b以外所有點都在過點a,b的直線p的一側，則線段ab為凸包上的一條邊。

III）????????? 對點集S中任意四點a,b,c,d，當d在三角形abc中（包括邊），則d不是凸包上的點。

??

?? ?上面的幾條關于凸包“凸”的性質為我們計算凸包提供了一個基礎。這里我們將介紹兩種簡單且被廣泛運用的算法――Gift-Wrapping和Graham-Scan算法。

?

Gift-Wrapping算法：

?? ?通過性質（I），我們可以找到一個特殊點，如具有最小y坐標且x坐標盡可能小的點。將它作為計算凸包的第一個頂點。確定了起點后，我們就可以通過Gift-Wrapping算法計算出點集的凸包。下面的步驟很直觀的描述了這個算法：

1）? 把點集中所有點都看成是固定在平面上的柱子，想象我們在起始點柱子上系上一根身子。

2）? 把繩子沿水平方向向右拉直，并逆時針旋轉，當繩子碰上一根柱子，則對應了凸包上的一點

3）? 繼續旋轉繩子，每次確定一個凸包上的頂點，直至繩子回到起點。

????????????? 圖一：Gift-Wrapping算法計算凸包的過程

每次通過旋轉繩子找到下一個凸包頂點需要對點集中所有剩余點進行一次比較，所以這

一步的時間復雜度是O（n）。每個凸包上的頂點都需要進行一次旋轉操作，而最壞情況下，凸包頂點個數可以和點集個數相等，所以整個Gift-Wrapping算法的時間復雜度是O（n2）的。

?

Graham-Scan算法：

?? ?Gift-Wrapping算法無論從理解還是從實現上來說，它都是十分簡單的。但由于它的復雜度并不理想，我們無法利用它來求解大規模的凸包問題。因而，我們將介紹一種高效的計算凸包的算法――Graham-Scan。

?? Graham-Scan算法主要可分成兩部分：

1）? 同Gift-Wrapping一樣，需要先找出一個起始點。將這個點作為原點，進行夾角排序。

2）? 先將起始點壓入堆棧H中，再按照已經排好的順序對每一個點進行掃描，同時維護堆棧H。這個堆棧表示的是到目前為止，所有已經掃描過的點對應的凸包。每當掃描一個點p的時候：

a)?????? 如果堆棧的元素少2個或者堆棧頂端的兩個點與p構成左轉關系，則將p壓入堆棧中。

b)????? 否則，棧頂元素出棧并繼續進行a的判斷。

當所有點都掃描完后，堆棧H即為我們要求的凸包。

???? 圖二：Graham-Scan算法的掃描過程（堆棧H儲存的即實線連接起來的點）

分析Graham-Scan的復雜度：第一步中找出起點并進行極角排序的復雜度是?????? ???O（n log n）。第二步中每一個點僅會被掃描一次并相應維護一次堆棧H 。而維護堆棧過程中每次訪問堆棧H中的點，要么這個點被刪除，要么就停止堆棧的維護，所以所有堆棧維護加起來最多只訪問了2n次。故這部分的復雜度是O（n）。綜合起來，Graham-Scan算法的時間復雜度是O（n log n）的。

算法分析：

現在考慮這道題目，題目要我們求出一個最小面積的矩形能夠覆蓋給定的所有點。易知矩形覆蓋所有點當且僅當它覆蓋這些點的凸包。故而，問題可以轉化為對于一個凸包，求出一個面積最小的矩形來覆蓋它。

那么這個覆蓋凸包的最小矩形有什么性質呢？

首先，這個矩形的四條邊上必然都有凸包的頂點。這個很容易想清楚，如果矩形的某條邊沒有碰上凸包的頂點，那么我們一定能把這條邊向里壓，從而得到一個更小的滿足條件的矩形。

其次，這個矩形至少有一條邊與凸包上的一邊重合。這個性質不容易直觀地想清楚，需要書面證明一下。由于完整的證明需要分成很多情況來討論，比較繁瑣，所以這里僅選取其中的一種情況來證明，其他情況可以類似地進行證明。

利用反證法，我們假設覆蓋凸包的最小矩形所有邊都沒有和凸包的邊有重合，也就是說，最小矩形的每條邊上僅有一個凸包的頂點。如圖三所示，矩形ABCD是覆蓋凸包的最小矩形，M、N、P、Q為凸包在矩形四條邊上的頂點。我們分別作MM’⊥ CD,NN’⊥ AD。則矩形ABCD的面積S = MP×Cos(∠PMM’)×NQ×Cos(∠QNN’)。我們將矩形旋轉X度（順時針為正，逆時針為負），仍使矩形覆蓋凸包且M、N、P、Q分別在它的四邊上。則此時新矩形的面積S = MP×Cos(∠PMM’+ X)×NQ×Cos(∠QNN’- X) 。我們僅需考慮Cos(∠PMM’+ X)×Cos(∠QNN’- X)的單調性。

Cos(∠PMM’+ X)×Cos(∠QNN’- X)

= 1/2[Cos(∠PMM’+ X + ∠QNN’- X) + Cos(∠PMM’+ X - ∠QNN’+ X)]

= 1/2[Cos(∠PMM’+ ∠QNN’) + Cos(∠PMM’- ∠QNN’+ 2X)]

∵0≤∠PMM’＜ π/2 , 0≤∠QNN’＜ π/2

∴-π/2 ＜∠PMM’- ∠QNN’＜ π/2

∴Cos(∠PMM’- ∠QNN’)不可能取到最小值

∴x在0左邊的一個區間中f(x) = Cos(∠PMM’- ∠QNN’+ 2X)遞增，或x在0右邊一個區間中f(x) = Cos(∠PMM’- ∠QNN’+ 2X)遞減。

因而，對于這樣的矩形，我們總可以順時針或逆時針旋轉一個小角度，從而獲得一個更小的矩形，這與假設矛盾。故最小矩形至少有一條邊與凸包一邊重合。

??? 了解到最小矩形所具有的這兩個性質后，我們就能夠很容易的想到一種算法，枚舉凸包上哪條邊與矩形的邊重合，再找出在這條直線投影的正負方向上最遠的和到直線距離最遠的三點，從而確定和計算出矩形的面積，最后選取最小值，即為覆蓋凸包的最小矩形的面積。

? 我們用最樸素的方法去實現它，枚舉每條邊后再把剩余的點都掃描一遍，來找出另外三點，計算出矩形的面積。這樣做時間復雜度是O（n2）得。就本題來說已經可以接受了。但如果規模再大一點，怎么辦呢？我們能不能做得更好呢？

? 答案是能！我們還有一個很重要的信息沒有利用到，對凸包上任意一條邊，依次計算出凸包頂點到它的距離或投影距離，構成的序列總是一個先增再降的。同時，注意到如果逆時針順序枚舉重合的邊時，每次找出來的另外三點也總是在向逆時針方向移動。

? 由此，我們就得到了一個更加高效的算法。枚舉過程中，逆時針旋轉到下一條邊后不需要再重新掃描所有點，只要分別從上一條邊確定的三點出發，向后比較，找到最大值，來更新這三個點即可。

在枚舉過程中，三個點的指針都只會對每個頂點訪問一次，所以這個過程的平攤復雜度是O（n）的。結合前面計算凸包的過程，在O（n log n）的時間內我們就能夠圓滿地解決這題了。

??? 了解到最小矩形所具有的這兩個性質后，我們就能夠很容易的想到一種算法，枚舉凸包上哪條邊與矩形的邊重合，再找出在這條直線投影的正負方向上最遠的和到直線距離最遠的三點，從而確定和計算出矩形的面積，最后選取最小值，即為覆蓋凸包的最小矩形的面積。