1樓：Wolf Snow
假設最大四邊形的頂點都在凸包上，設凸包有n個頂點，那麼為了形成凸包內接四邊形，需要去掉的點數為n-4
那麼為了求最大四邊形，等於求去掉的n-4個頂點構成的最小三角形面積之和了。把各頂點所構成的三角形列出來，排序（bucket sort: O(n))，取最小的n-4個即可，複雜度為O(n)
====補充===
三角形是這樣找的：
1） 初始時，隨機找到凸包一點，設為B，由這一點與相鄰兩個點構成的三角形ABC，求面積，設為S1。
2） 去除頂點B, 構成新的凸包，在新的凸包上，用旋轉卡殼法（或其他方法）找到構成的最小三角形面積S2， 與S1相加。依次找出S3, S4直到Sn-4, S=S1+S2+...+Sn-4
3) 在除去B點的其他點，重複步驟1）2），得出S，直到S最小。
2樓：馬基雅弗利
直接說一下自己o(n)的思路吧，因為是凸包，所以可以任意確定第一條邊，然後以順時針或逆時針遍歷其它的邊，得到和其夾角最小的邊，得到第乙個解，注意，從這裡開始，只需要按照特定方向旋轉得到其它的解即可，不需要重新全部遍歷一遍。另外，關於為什麼最大的四邊形頂點一定是凸多邊形的頂點，可以從外接圓的角度考慮。
3樓：金髮妹子
口胡一下...
無責任猜測著四個點一定要在凸包頂點上. 那麼考慮樸素的列舉第一條對角線, 那麼另外兩個點可以分別在這條對角線兩側, 並且距離是最遠的. 於是這個可以二分出來, 複雜度是, 當然也可以用旋轉卡殼去掉這個log.
得到了乙個的做法.
以下繼續口胡....
考慮另一條對角線的性質, 大概是一對對踵點, 然後對鐘點我們可以用旋轉卡殼求出來, 於是就是列舉每一對對鐘點作為第二條對角線, 可以用的做法求出第一條對角線. 當然這個log也是可以用旋轉卡殼去掉的. 大概就得到了乙個的做法.
如何評價一笑而過的凸凸老師？
Vistodoll 絕對是寶藏老師！今年上了一笑而過的六級全程班凸凸上的第一節課我就很喜歡這個老師也可能是合眼緣吧他上課很幽默讓你老想笑他講的東西讓你感覺自己一下子知識層擴大了很多就是很有魅力的課程我強烈安利！凸凸真的是乙個超級有人格魅力的老師英語水平很高又很有親和力！在微博又很搞笑一直被老媽催婚的...
歐幾里得空間中的凸集和它的閉包有相同的內部？
長軀鬼俠 參考Jean Baptistle Hiriart Urrut所著教材Fundamentals of Convex Analysis的章節A.2.1。這個問題正好說明，相對內點 0,text C cap B x,delta subset C eeimg 1 對凸集來說是更合適的定義。可以降維...
請問如何計算高鐵兩站之間的最大運力
Zhaoyang Wang 在計算列車定員之前，首先計算一下區間的通行能力吧 我就不寫公式了。1.因為高鐵 客專基本都是複線，所以首先從最簡單的平行追蹤執行圖算起，它是乙個與執行圖週期 乙個週期的列車數 天窗時間 有效係數有關的函式。執行圖週期與區間純執行時間 車站間隔時間 起停附加時分有關。區間純...