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