標(biāo)準(zhǔn)問法：給你1e3個點，你得在時間內(nèi)求出它們能組成的三角形的最大/小面積。

由于不允許3方枚舉，我們這么考慮：

先花平方時間把所有直線算出來，作為三角形的底邊，那么我們需要維護(hù)一個點的序列，這個序列得是根據(jù)他們與當(dāng)前直線的距離排序的。

難點就在如何維護(hù)這個點的序列

來看一張圖：

假設(shè)我們一開始有一張已經(jīng)按x坐標(biāo)排好序的二維點陣圖，當(dāng)前相對縱軸是y軸，相對橫軸是x軸

我們開始順時針旋轉(zhuǎn)這個坐標(biāo)系，會發(fā)現(xiàn)兩個點的相對橫坐標(biāo)的排序產(chǎn)生順序交換當(dāng)且僅當(dāng)他們的連線與當(dāng)前參考縱軸平行。

繼續(xù)旋轉(zhuǎn)這個坐標(biāo)系

現(xiàn)在已經(jīng)知道一條連線與參考縱軸平行時，連線的兩點會發(fā)生交換，那這些連線與參考縱軸對齊的順序有沒有什么規(guī)律呢？

回到原圖，你發(fā)現(xiàn)C、D兩點的連線斜率是最小的，其次是C、B兩點。另外一個重要結(jié)論出來了：這些直線與參考縱軸對齊的順序就是他們斜率的排序。

于是我們可以記錄每條連線的兩個點，以及每個點參考橫坐標(biāo)的排名，在處理一條直線的時候可以利用這個排名把離直線最近或最遠(yuǎn)的點找出來統(tǒng)計答案，然后把形成這條直線的兩個點的參考橫坐標(biāo)排名交換，然后問題就解決了。

相關(guān)問題：

BZOJ 3707?

https://vjudge.net/problem/%E9%BB%91%E6%9A%97%E7%88%86%E7%82%B8-3707

HDU 6538

https://vjudge.net/problem/HDU-6538

CF1019D

http://codeforces.com/contest/1019/problem/D

天梯L3-021 神壇

https://pintia.cn/problem-sets/994805046380707840/problems/994805046577840128

最后放一下神壇的正解：

首先綜上所述，我們這么搞的正確性是可以保證的。問題是天梯的內(nèi)存限制特別離譜：64MB。

那么這題制約我們的其實不是時間，是空間：我們沒法保存所有的直線對象，一個直線對象至少需要它的斜率和產(chǎn)生它的兩個點。

在用int存點被卡了之后，發(fā)現(xiàn)n只有5000，short完全裝得下，于是改用short裝點的引用，此時本想預(yù)處理每條直線的斜率k，無奈發(fā)現(xiàn)再多一個平方級別的int已經(jīng)裝不下了。

于是直線的斜率只能在排序的時候通過點來算，如果出現(xiàn)除法很可能會超時，于是把分母移項到對面為乘的形式，比較函數(shù)終于寫好了——然后因為用了double，精度被卡了……

無奈改用long long存點，好在前一步把比較函數(shù)寫成了乘法，不會產(chǎn)生整除誤差，終于卡了過去。

通過代碼：https://paste.ubuntu.com/p/8hM8dRNFP4/

實際表現(xiàn)：

另外附上本蒟蒻隊的模板倉庫：

https://github.com/voidf/GenshinWaterFriendsTeamTemplate