计算几何专题练习记录（二）
计算几何专题练习记录第一部分链接：link
点 / 向量
- CF 672C Recycling Bottles：$2$ 倍的所有点到垃圾桶距离减去 $A,B$ 第一次走的时候顺便带垃圾的距离最大值；注意还有可能只有 $A$ 或 $B$ 捡垃圾的情形。$\star$
- CF 136D Rectangle and Square：暴力枚举+矩形判断+正方形判断。 $\star$
- CF 127A Wasted Time：两点之间距离。$\star$
极角排序
CF 598C Nearest vectors：极角排序方法：先判断向量在哪个半区，然后用叉积判断顺序；算两向量夹角时用
atan2而非acos精度更高；开long double. $\star\star$hdu3629 Convex：给定 $n$ 个点，保证没有三点共线，求能形成多少凸四边形。
$凸四边形数=总四边形数(C_n^4)-凹四边形数$。凹四边形的特征是一个点被一个三角形严格包含在内，所以 $凹四边形数=\sum包围一个点的三角形数$。而 $包围一个点的三角形数=总三角形数(C_{n-1}^3)-不包含该点的三角形数$。所以问题转化为求不包含一个点的三角形数量。以该点（设为 $O$ ）为参考系按极角排序，双指针扫描——$i$ 指向某点时，$j$ 指向逆时针方向第一个使 $\angle iOj\geq\pi$ 的点，则两指针之间的所有点任取两个与 $i$ 都能形成不含 $O$ 的三角形，可以知道这样做不重不漏。$\star\star\star$
UVA1606 Amphiphilic Carbon Molecules：一定存在过两个点的最优直线，然而枚举两个点显然会超时。现在我们只枚举一个点，其他点关于枚举的点作极角排序（黑点取对称点），双指针扫描一遍，边扫描边统计。$\star\star\star$
CF 1284E New Year and Castle Construction：对于每个点，$包含它的四点集合个数=总个数(C_{n-1}^4)-不包含它的四点集合个数$。所以枚举每个点，以它为参考系极角排序，双指针扫描，两个指针之间所有点任取三个与第一个指针指向的点都能形成不包含原点的四点集合。【与hdu3629极其类似】$\star\star\star$
多边形
- hdu1115 Lifting the Stone：多边形重心模版。
- Gym 101808E Floods：积水面积问题。想象从每个点往上引直线，那么积水面积可以分割成一系列三角形和梯形之和。枚举每条边，预处理其前、其后最高点位置，取这两个位置小的那个为积水高度。若积水高度大于当前边的两端高度则是梯形；若一大一小则是三角形；若小于则为零。$\star\star\star$
- CF 975E Hag’s Khashba：由于多边形顶点相对位置不会改变，我们只需要记录旋转后的重心位置和第一个顶点位置即可，其他位置可以通过预处理的信息 $O(1)$ 得到。注意实现时尽量少地求角度再旋转该角度，因为求角度用一个
atan再加上旋转时对它取sin和cos就会累积出较大误差。$\star\star\star\star$
圆
- CF 600D Area of Two Circles’ Intersection：注意坐标范围较大，要用
long double. $\star\star$ - CF 908C New Year and Curling：$\star$
- CF 140A New Year Table：算出角度，精度问题需要
+eps. $\star$
闵可夫斯基和
- [JSOI2018]战争：会发生战争的条件是：$\exists a\in A,b\in B$ 使得 $b+\overrightarrow d=a$，即 $\overrightarrow d=a-b$. 故只需要求出凸包 $A$ 和 $-B$ 的闵可夫斯基和，然后判断 $\overrightarrow d$ 是否落在和凸包内。判断点在凸包内方法：以凸包左下点为参考系，按照极角序排序，二分出点被哪两个向量夹住，在判断点是否在凸包内。复杂度：$O(n\lg n)$. $\star\star\star\star$
三维几何
- Gym 101726C Ekaterinburg Pyramids：一个点能看到四面体某个面的充要条件是：这个点与该面的对点分处面的两侧。判断是否分处两侧可通过判断混合积正负是否相同。$\star\star\star$