前往
大廳
主題

LeetCode - 812. Largest Triangle Area 解題心得

Not In My Back Yard | 2021-01-18 00:00:05 | 巴幣 0 | 人氣 243

題目連結:


題目意譯:
你有一個座標平面上的列表 points。回傳從列表挑出任意三點可形成的最大三角形之面積。

注:
3 ≦ points.length ≦ 50.
沒有重複的點。
-50 ≦ points[i][j] ≦ 50.
答案與真實值誤差在 10 ^ (-6) 之內皆算為正確。



範例測資:
輸入: points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
輸出: 2
解釋:
給定的五個點表示於下圖。其中紅色的三角形為最大的三角形。


解題思維:
正常來說應該窮舉全部點所形成的的凸包上的頂點,如這題

但是因為點最多 50 個,所以就直接窮舉所有可能的取法即可(三層迴圈即可)。至於對於每個取法,要求面積可以參見這題的做法。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作