旋转坐标系专题，天梯L3-021 神坛题解

标准问法：给你1e3个点，你得在时间内求出它们能组成的三角形的最大/小面积。

由于不允许3方枚举，我们这么考虑：

先花平方时间把所有直线算出来，作为三角形的底边，那么我们需要维护一个点的序列，这个序列得是根据他们与当前直线的距离排序的。

难点就在如何维护这个点的序列

来看一张图：

假设我们一开始有一张已经按x坐标排好序的二维点阵图，当前相对纵轴是y轴，相对横轴是x轴

我们开始顺时针旋转这个坐标系，会发现两个点的相对横坐标的排序产生顺序交换当且仅当他们的连线与当前参考纵轴平行。

继续旋转这个坐标系

现在已经知道一条连线与参考纵轴平行时，连线的两点会发生交换，那这些连线与参考纵轴对齐的顺序有没有什么规律呢？

回到原图，你发现C、D两点的连线斜率是最小的，其次是C、B两点。另外一个重要结论出来了：这些直线与参考纵轴对齐的顺序就是他们斜率的排序。

于是我们可以记录每条连线的两个点，以及每个点参考横坐标的排名，在处理一条直线的时候可以利用这个排名把离直线最近或最远的点找出来统计答案，然后把形成这条直线的两个点的参考横坐标排名交换，然后问题就解决了。

相关问题：

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

最后放一下神坛的正解：

首先综上所述，我们这么搞的正确性是可以保证的。问题是天梯的内存限制特别离谱：64MB。

那么这题制约我们的其实不是时间，是空间：我们没法保存所有的直线对象，一个直线对象至少需要它的斜率和产生它的两个点。

在用int存点被卡了之后，发现n只有5000，short完全装得下，于是改用short装点的引用，此时本想预处理每条直线的斜率k，无奈发现再多一个平方级别的int已经装不下了。

于是直线的斜率只能在排序的时候通过点来算，如果出现除法很可能会超时，于是把分母移项到对面为乘的形式，比较函数终于写好了——然后因为用了double，精度被卡了……

无奈改用long long存点，好在前一步把比较函数写成了乘法，不会产生整除误差，终于卡了过去。

通过代码：https://paste.ubuntu.com/p/8hM8dRNFP4/

实际表现：

另外附上本蒟蒻队的模板仓库：

https://github.com/voidf/GenshinWaterFriendsTeamTemplate