題目連結:
題目意譯:
你被給定一陣列 trees,其中 trees[i] = [xi, yi] 代表著一棵樹在花園中的位置。
你被要求使用著長度盡可能短的繩子將整個花園用圍籬圍起來,因為繩子很貴。花園有被圍好若且唯若所有樹都有被圍於繩子內。
回傳恰好位於圍籬邊上的那些樹之座標。
限制:
1 ≦ trees.length ≦ 3000
trees[i].length == 2
0 ≦ xi 、 yi ≦ 100
所有給定的座標皆相異。
範例測資:
範例 1:
輸入: points = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]
輸出: [[1,1],[2,0],[3,3],[2,4],[4,2]]
範例 2:
輸入: points = [[1,2],[2,2],[4,2]]
輸出: [[4,2],[2,2],[1,2]]
解題思維:
本題實際上就是在求凸包(如
這題)——正確來說是「幾乎」凸包,因為本題還需要包含進那些剛好在凸包邊上的點。
可以將在建立凸包的過程中允許共線的情況(外積 = 0),最後消掉重複的點;或是求完凸包後,重新掃過一次所有點,判斷哪些點在凸包上也是可行的。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。