摘要: :)
閱讀全文
摘要: 先求凸包，然后再用旋轉(zhuǎn)卡殼方法求解。
具體做法是枚舉三角形的第一個點i，設(shè)j = i + 1，k = j + 1。然后做以下操作：
1.計算i，j，k構(gòu)成的三角形面積a1和i，j，k + 1構(gòu)成的三角形面積a2，如果a2 < a1，則進行下一步，否則k++，重復(fù)此步。
2.記錄此時的三角形面積b，如果b < preb（就是上一個j對應(yīng)的三角形面積）j++，轉(zhuǎn)第一步，否則退出。
可以證明這個算法的復(fù)雜度為O(n2)。具體實現(xiàn)見代碼。
閱讀全文