觀星

對于平面上有n個點分為三類，要求尋找一個三角形，三個頂點分別屬于這三類，求解最大面積。
N<=3000

首先考慮到$O(n^2)$的枚舉，然后對于另外一種考慮這個點的位置，顯然它應該在凸包上，因為我們相當于要尋找距離某個直線最遠的點，所以相當于用一個直線來截。

然后考慮在凸包上二分，首先如果直接求凸包，斜率不是單調的，沒法二分，或許可以三分。我們可以分別求出上凸包和下凸包，分別找到最遠點，上凸包的斜率單增，下凸包的斜率單減，所以可以直接二分。

此時就不用極角排序了，直接按照橫坐標為第一關鍵字，縱坐標為第二關鍵字排序即可，然后利用單調棧求解。
需要注意一個細節(jié)，就是橫坐標相等的點只需要保留縱坐標最大或最小的，所以需要判斷一下

然后考慮求解面積，多邊形面積需要利用叉積求解，就是前后相鄰點叉積之和，但是這樣求出來的可能是負的，所以需要加上絕對值。

總結

以上是生活随笔為你收集整理的观星（计算几何/凸包/多边形面积）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。