問題一：求N個(gè)點(diǎn)中斜率最大的兩個(gè)點(diǎn)。
要解決該問題，我們首先證明一個(gè)結(jié)論：三個(gè)點(diǎn)a、b、c，若x_a < x_b < x_c則斜率最大者必定是ab或者是bc，而不會(huì)是ac。證明如下：
我們用k表示斜率，
不妨假設(shè)k_ac > k_ab，即(y_c - y_a)/(x_c - x_a) - (y_b - y_a)/(x_b - x_a) > 0
則可以推出x_a * y_b + x_b * y_c + x_c * y_a > x_a * y_c + x_b * y_a + x_c * y_b
那么可以得出k_bc - k_ac = (y_c - y_b)/(x_c - x_b) - (y_c - y_a)/(x_c - x_a)  = (x_a * y_b + x_b * y_c + x_c * y_a) - (x_a * y_c + x_b * y_a + x_c * y_b) > 0
所以可以知道如果ac斜率大于ab，那么它就不可能大于bc
同理可以得出若ac斜率大于bc，那么它就不可能大于ab
證畢。
有了上面的證明，我們就可以先對(duì)N個(gè)點(diǎn)的橫坐標(biāo)排序，然后再計(jì)算a[i]與a[i + 1]的斜率，取最大值即可。
代碼略。

問題二：求N個(gè)點(diǎn)中距離最遠(yuǎn)的兩點(diǎn)距離。
典型的求凸包直徑問題，這里先講解一下如何利用Graham scanning方法在O(nlogn)時(shí)間內(nèi)求凸包，然后利用旋轉(zhuǎn)卡殼法在O(n)時(shí)間內(nèi)求凸包直徑。
該問題面試中一般不會(huì)問到，太過復(fù)雜，不過應(yīng)該學(xué)習(xí)這種思想。
1）Graham scanning求凸包：
首先：選取N個(gè)點(diǎn)中y坐標(biāo)最小的點(diǎn)為P₀，若有多個(gè)點(diǎn)y坐標(biāo)相同，則取x坐標(biāo)最小的點(diǎn)為P₀，即P₀為坐標(biāo)系中左下角的點(diǎn)。
然后：根據(jù)direction(P₀, P_i, P_j)來排序，direction()函數(shù)是求P₀P_i向量和P₀P_j向量的叉積，叉積的作用是判定P₀P_i向量在P₀P_j向量的逆時(shí)針方向還是順時(shí)針方向，如果P₀P_i X P₀P_j > 0則說明P₀P_i在P₀P_j的順時(shí)針方向，否則在逆時(shí)針方向。另外叉積的值的絕對(duì)值還表示以P₀P_iP_j三點(diǎn)組成的三角形的面積，因?yàn)镻₀P_i X P₀P_j = |P₀P_i| * |P₀P_j| * sin∠P_iP₀P_j，這個(gè)結(jié)論會(huì)在卡殼時(shí)用到。有了上面的知識(shí)，可以知道排序后的結(jié)果是所有節(jié)點(diǎn)圍繞P₀以逆時(shí)針方向排列。
再次：將點(diǎn)P₀和點(diǎn)P₁入棧，然后從P₂到P_n循環(huán)執(zhí)行下面操作：若direction(P_{stack[top - 1]}, P_stack[top], P_i) < 0，則刪除棧頂元素，即top--（因?yàn)榕判虻臅r(shí)候，如果兩個(gè)節(jié)點(diǎn)對(duì)P₀的向量叉積若相等，則距離P₀遠(yuǎn)的節(jié)點(diǎn)排在后面，所以這里如果上述等式等于0的話則可以肯定P_i到P_{stack[top - 1]}的距離比P_stack[top]到P_{stack[top - 1]}的距離遠(yuǎn)，所以可以直接將P_stack[top]出棧，當(dāng)然也可以不出棧，因?yàn)槟硞€(gè)在凸包多邊形的某條邊上的點(diǎn)，可以算作凸包的點(diǎn)，也可以去掉），否則P_i進(jìn)棧。直到P_n判斷完畢。
最后：棧stack中的所有點(diǎn)就是凸包多邊形的點(diǎn)，并且從棧底到棧頂以逆時(shí)針排列。
上面算法表述的比較羅嗦，看下面的圖示就明白了：
首先是排序，然后是P₀和P₁入棧：



然后是判斷P₂是否應(yīng)該入棧：



因?yàn)镻₀P₁ X P₀P₂ > 0，所以P₂入棧：



然后判斷P₃是否應(yīng)該入棧：



因?yàn)镻₁P₂ X P₁P₃ < 0，所以P₂出棧P₃入棧：



判斷P₄是否應(yīng)該入棧：



因?yàn)镻₁P₃ X P₁P₄ > 0，所以P₄入棧：



判斷P₅是否應(yīng)該入棧：



因?yàn)镻₃P₄ X P₃P₅ > 0，所以P₅入棧：



判斷P₆是否應(yīng)該入棧：



因?yàn)镻₄P₅ X P₄P₆ < 0，所以p₅出棧P₆入棧：



最后p7入棧，形成最終的凸包：



通過以上圖示過程可以清晰明白凸包的構(gòu)建過程。證明過程比較復(fù)雜，詳見《算法導(dǎo)論》。