牛客计算几何课程
[2016WF]Oil
题意简化：
给定若干条平行于 $x$ 轴的线段，求通过一条直线最多能经过几条线段。
知识点：
极角序扫描。
解法：
引理：任意一条穿过若干线段的直线，一定可以在不减少穿过线段数的前提下平移、旋转到至少经过两个线段的点。
假设当前直线没有经过任意一个线段的端点。则对该直线进行平移一定可以移到一个点上。如果此时还是只经过了一个点，那么将直线绕着这个唯一经过的点旋转，也一定会碰到另一个线段的端点。
综上，一个最显然的做法是枚举经过的这两个点，再计算穿过了几条线段。
时间复杂度：$O(n^3)$。
考虑上述过程中，确定经过的一个点，通过旋转移到另一个点，容易发现一条线段在这个过程中是随着旋转被直线连续穿过的。
所以，可以尝试枚举一个点，另一个点通过极角序扫描的过程判断确定。
具体而言，假设逆时针旋转，当扫描线扫到线段右端点时，穿过线段数$+1$；当扫描线扫到线段左端点时，穿过线段数$-1$。
注意，平面内线段端点可能会重合，而对于重合的这个端点，要先考虑右端点。
同时，极角序扫描的过程中，扫描的实际上是一条射线而不是一条直线，所以要把下半平面的线段以原点为中心，中心对称到上半平面中，然后扫上半平面即可。
时间复杂度：$O(n^2\log n)$。
总结：
极角序扫描线，与序列扫描线类似。
[POI2008]Tro
题意简化：
求平面上 $n$ 个点构成三角形的面积之和。
知识点：
叉积的分配率。
解法：
三角形的面积等于以其一顶点为极点，另外两边的叉积的绝对值的一半。
若固定三角形的两点，枚举另一个点，那么这些三角形的面积之和可以表示为：
$\overrightarrow{OA}\times \overrightarrow {OP_1}+\overrightarrow {OA}\times \overrightarrow {OP_2}+\overrightarrow {OA}\times \overrightarrow {OP_3}+…+\overrightarrow {OA}\times \overrightarrow {OP_n}$
叉积满足分配律，上式 $=\overrightarrow {OA}\times (\sum\overrightarrow{OP_i})$。
具体而言，枚举一条边极角为 $\theta$，那另一条边的范围 $[\theta,\theta+\pi]$。
指针的终止可以通过叉积确定，另一条边的极角在 $[\theta,\theta+\pi]$ 中时，$\vec a\times \vec b\geq 0$。
实现一：
随着枚举极边的旋转，另一条边的极角上界不断增大，使用双指针维护区间向量和即可。
每个三角形的面积会被三条边计算三次，所以最后的结果要再 $\times \dfrac{1}{3}$。
实现二：
对于每个三角形的面积计算，只考虑最右侧点的贡献。
所有三角形，最右侧的顶点的两边一定朝向 $x$ 轴负半轴。
所以对于最右侧的点，直接扫描 $[\frac{\pi}{2},\frac{3\pi}{2}]$ 的点，维护后缀向量和即可。
时间复杂度：$O(n^2\log n)$。
两个人的星座
题意简化：
给定二维平面上的 $n$ 个点，每个点都有一个颜色，共有三种，求满足三点颜色互不相同的不相交的三角形对数。
知识点：
极角序扫描。
解法：
引理：对于两个相离的凸多边形，有且仅有两条内公切线与两条外公切线。
而内公切线将两个凸多边形分成了不相交的，分居内公切线两侧。
也就是说，枚举这条内公切线，只需要计算两侧能形成的合法三角形个数，相乘累加即可。
每对三角形会被两条内公切线算两次，所以最后结果 $\times \dfrac{1}{2}$。
类似于 [2016WF]Oil，扫描线扫的过程中实际是一条射线，所以要把下半平面的点以原点为中心，中心对称到上半平面。
扫描的过程中统计对应颜色的数量即可。对于一侧的合法三角形个数即为与枚举的顶点颜色不一样的两种颜色数量的乘积。因为题目保证任意三点不共线，所以任意三点均可构成三角形。
时间复杂度：$O(n^2\log n)$。
总结：
极角序扫描的过程实际是一个射线在扫描的过程，对于直线情况，需要把下半平面对称到上半平面中去。
How Many Triangles
题意简化：
给定平面上 $n$ 个点，求可以形成多少个锐角三角形。
知识点：
极角序双指针。
解法：
锐角三角形有三个锐角，而有锐角的不一定是锐角三角形。所以不容易直接对锐角统计。
但是观察到钝角三角形和直角三角形只有一个钝角和一个直角，所以可以统计直角和钝角的个数。
容斥得到锐角三角形的个数。
由于题目没有保证任意三点不共线，所以还要减去平角（三点共线）的数量。
考虑枚举一个顶点，以极角序扫描边，对于当前扫到的边极角为 $\theta$，则直角到平角的范围在 $[\theta+\frac{\pi}{2},\theta+\pi]$。因为这个答案的范围和扫描的边不连续，所以一个做法是先将所有边逆时针旋转 $\frac{\pi}{2}$，然后以旋转后的边作逆时针 $\frac{\pi}{2}$ 的范围。
可以使用叉积和点积根据范围移动指针，$[0,\frac{\pi}{2}]$ 的范围下，$\vec a\cdot \vec b\geq 0,\vec a\times \vec b\geq 0$。但是移动的过程不一定存在超过这个范围的边，所以要手动加入 $x$ 轴正方向、$y$ 轴正方向、$x$ 轴负方向、$y$ 轴负方向四条边。
Amphiphilic Carbon Molecules
题意简化：
在平面上有 $n$ 个点，每个点是黑色或者白色。用一条直线把平面分成两部分，要求直线上的点加上直线左侧白色点和直线右侧黑色点或直线左侧黑色点和直线右侧白色点最多。
知识点：
极角序扫描。
解法：
和 两个人的星座 一致，枚举极点，极角序扫描维护两侧颜色数量即可。
[2020WF]Ley Lines
题意简化：
求用一个宽度为 $t$ 的丝带最多能覆盖多少点。
知识点：
平面旋转。
解法：
引理：答案丝带一定存在某边经过至少两个点。
考虑枚举两个点，将所有点投影到垂直于过这两个点的直线的直线上，然后从两条直线的交点开始二分找到最后一个距离不超过 $t$ 的点。（向左向右各做一次）
时间复杂度：$O(n^3)$。
但是注意到，初始情况下，所有点在 $x$ 轴上的投影的顺序等价于丝带平行于 $y$ 轴的上述投影结果。
而对于别的丝带，二分每个丝带只要做一次，区别在于投影之后的顺序不同。考虑整体旋转时，点与点之间的位置交换关系。
对于点 $A$ 和点 $B$， 当整体旋转极角平行 $\overrightarrow{AB}$ 时，$AB$ 投影之间的相对位置发生变化。
所以对于所有点对 $\overrightarrow{P_1P_2}$，进行极角排序（从平行初始 $y$ 轴开始作为极角序最小值）扫到边时，每次进行二分后交换 $P_1$ 和 $P_2$，更新答案。因为没有直接维护投影，而是仅维护了投影之后的相对顺序，所以二分时候求距离需要计算点到直线的距离而不是点到点。
时间复杂度：$O(n^2\log n)$。
总结：
极角排序有时要注意极角序扫描的开始位置，也就是设定的极角序最小值。
Nearest Point
题意简化：
平面上 $n$ 个点，平面整体随机旋转一个角度，求点对 $(P_i,P_j)$ 之间，$P_j$ 是横坐标距离 $P_i$ 最小的概率是多大。
知识点：
平面旋转。
解法：
考虑 $P_j,P_k$ 和 $P_i$ 之间的位置关系：
- 当 $y$ 轴平行 $\overrightarrow{P_jP_k}$ 时，$P_i$ 的横坐标和 $P_j,P_k$ 距离相同（同向）。
- 当 $y$ 轴平行 $\overrightarrow{OP_i}+\dfrac{\overrightarrow{OP_j}+\overrightarrow{OP_k}}{2}$，时 $P_i$ 的横坐标和 $P_j,P_k$ 距离相同（异向）。
所以对于任意的三点，存在 $12$ 种影响答案的 $y$ 轴旋转的结果。
处理出所以可能的 $y$ 轴，按极角排序（此题没有严格的先后顺序，所以不用从原 $y$ 轴开始作为极角序最小的边）后，对于相邻的两条边之间，点和点之间的相对最近点对不会发生变化。
但是如果单纯使用扫到的边，存在的是多点相等关系，而不是最近。所以要取相邻两边的角平分线作为 $y$ 轴，后将所有点投影到对应的 $x$ 轴上，对于每个投影找最近点更新答案即可（此时保证了不存在距离相同的点，所以按投影 $x$ 坐标排序后按相邻点更新即可）。
时间复杂度：$O(n^4\log n)$。
总结：
考虑关键点时，关键点往往是一个边界情况。若题目更关心的是这个边界“下一步”的情况，那么可以选择对两个相邻关键点的“中点”进行考虑。
Rikka with Triangles
题意简化：
给定一个平面上 $n$ 个点，求这个 n 个点能构成的锐角三角形面积之和。
知识点：
极角序扫描
解法：
和 How Many Triangles 类似，通过容斥得到锐角三角形面积和。
所有三角形面积和与 [POI2008]Tro 一致。
核心在于求钝角三角形面积和直角三角形面积和。
这部分扫描和 How Many Triangles 类似，因为钝角和直角对应顶点唯一确定了钝角三角形和直角三角形。
所以此部分和 How Many Triangles 类似，维护 $[\theta+\frac{\pi}2,\theta+\pi]$ 之间的向量和即可。
时间复杂度：$O(n^2\log n)$。