牛客计算几何课程
Winding Number
题意简化：
以任意顺序给定 $n$ 个点，$m$ 次询问，每次询问一个点为极点，按给定顺序遍历 $n$ 个点顺时针经过的圈数 $-$ 逆时针经过的圈数的值。
知识点：
to_left 测试；
解法：
感觉题目意思有点不明确，实际上无论顺时针还是逆时针都并不一定会走完整圈吧。
大概是题目将未走完的一圈也视作一圈，也就是走的角度$/360$向上取整。
因为最后会回到起点，所以顺时针走的角度 $-$ 逆时针走的角度一定是 $360$ 的倍数。
所以如果有没走完的圈，那顺时针和逆时针都会有没走完的圈，所以并且一定抵消。
（不过实际上应该是单独的顺时针和逆时针不一定是一个整圈，但是顺时针和逆时针加起来一定是一个整圈，也就是点在圈外的情况）
所以只要考虑整圈即可。
并且，如果这个极点不在这个整圈（多边形）内，那么顺时针和逆时针一定是抵消的。
所以只要考虑极点在圈内。
既然是一个整圈，那么必然有且仅有一条边，走过它的时候，经过了过极点的水平的直线。且因为是一个整圈，所以左右各有一条边，我们只考虑右侧的一条边。
所以只要考虑有多少边经过过极点的水平的直线即可，并且如果过极点的水平的直线过边的端点，那么只应该考虑一次，所以如果经过端点，只考虑先经过的一个。
如果是顺时针经过，那么顺时针走过的圈数就加一；逆时针同理。
特判经过边的情况。
设当前边为 $(u,v)$，若 $u_y<v_y$ 则是顺时针；反之是逆时针（$u_y=v_y$ 的情况可以跳过）。
使用 to_left 测试判断点在边的左侧。
时间复杂度：$O(nm)$。
总结：
若一个点在多边形外部，则顺时针和逆时针经过的角度相互抵消。
若一个点在多边形内部，则顺时针和逆时针经过的角度一个为 $0$，另一个为 $360$。
Mr. Main and Windmills
题意简化：
给定 $n$ 个点，一个人从起点到终点的过程中，任意一对点之间关于人的位置会发生变化。m 次询问第 $x$ 个点第 $y$ 次与某个点相对位置发生更改时人的位置。
知识点：
直线与线段的交点。
解法：
容易发现：相对位置发生变化时，即为在过程中两点与人共线的时候。所以对于每次询问，求出其它点和第 $x$ 个点形成的直线与路径的交点，第 $y$ 个交点即为答案。
是否预处理差别不大。
时间复杂度：$O(nm)/O(n^2)$。
总结：
在求直线/线段与直线/线段交点的问题中，通常为求出对应直线与直线的交点。若是线段，需要额外判断线段与直线/线段是否有交。这个可以使用 to_left 测试实现，无精度误差。若是求出交点后判断是否在直线/线段上，会有精度误差。
[2017WF]Airport Construction
题意简化：
按逆时针顺序给出多边形 $n$ 个点，求能完全落在多边形内的线段的长度。
知识点：
判断点在多边形内。
解法：
一般多边形的直径一定经过多边形某两个顶点。
所以枚举这两个顶点，判断线段是否在多边形内即可。
考虑这样一个情况：线段上有一部分在多边形外部。那么这一部分的左部分和右部分会在多边形内部，也就是考虑在多边形外部的这部分的两个端点一定落在多边形的边上。
所以对于枚举的两个顶点确定的直线，求出与多边形的所有交点后，按 $x$ 坐标升序排序，考虑相邻两点的线段是否在多边形内即可。因为是连续的一段，所以等价于任取一点判断，一般取中点即可。
对于一般多边形判断点是否落在多边形内，使用光线回转法判断，无精度误差。
时间复杂度：$O(n^3)$。
总结：
一般多边形的直径一定经过多边形某两个顶点。
判断一条线段是否完全落在多边形内，判断中点是否落在多边形内即可。
Operation Love
题意简化：
以顺时针或逆时针（需要自行判断）给定一只“右手”的大小、形态描述，在可翻转、旋转的情况下，判断是左手还是右手。
知识点：
to_left 测试。
解法：
因为形态和大小是确定的，所以可以通过边长来确定某条边是“手”的哪一部分。
长度最长为 $9$ 的是底边，和底边相邻的是大拇指和小拇指。长度为 $6$ 的是大拇指，长度为 $8$ 的是小拇指。（所以其实只靠长度也是可以判断出大拇指和小拇指的，但是单靠大拇指或小拇指并没有什么用）
无论给出的点是按顺时针还是逆时针，只要大拇指在底边的右边，那么就是右手，反之就是左手。
所以找到底边和大拇指后进行一次 to_left 测试即可。
同时，因为起点不确定，所以需要“断环成链”。
时间复杂度：$O(n)$
总结：
通过长度找到指定边。
通过 to_left 确定描述点集的顺逆时针顺序。
三角碰撞(Triangle Collision)
题意简化：
给定三角形和三角形内一个点，该点以一定的速度发射，碰到三角形边时会进行弹射，询问第 $k$ 次弹射的时间是多少。
知识点：
弹射问题转换成直线相交问题。
解法：
将整个平面用三角形填充划分，每一次反射都可以将反射线对称到三角形弹射边的另一侧，使得与入射线重合。
也就是说，在弹射过程中形成的反射线都可以映射到与入射线重合的直线上。而每个弹射点都会对应一个直线与三角形的交点。所以第 $k$ 次弹射即为入射直线与三角形产生的第 $k$ 个交点。
但是由于有 $T$ 组询问的三角形和三角形内的点不相同，所以不能预处理 $k$ 个交点。
但是对于一个确定的线段，可以较简单地求出线段与三角形三种边的交点个数。（求三角形边对应直线分量即可，类似高中物理大题）
时间复杂度：$O(T\log k)$。
总结：
多边形内弹射问题经典转换，将弹射问题转换成直线与多边形边相交问题。
（正凸多边形是没问题，但是如果是凹多边形，目前还不太确定能不能一样做，大概是没问题的）
Magic Rabbit
题意简化：
给定三种药剂，对于两种成分 $a,b$，浓度分别为 $a_i,b_i\ \text{mg}/\text{ml}$。判断是否能用无限量的三种药水配置出 $A,B\ \text{mg}/\text{ml}$ 的药水。
知识点：
判断点在三角形内。
解法：
直接考虑三种药水混合较复杂，尝试先考虑任意两种药水能混合成的药水，然后考虑和剩下的一种药水混合。
考虑 $(a_1,b_1),(a_2,b_2)$ 配成 $(A,B)$，首先，$a_1\leq A\leq a_2,b_1\leq B\leq b_2$。
$\dfrac{k_1(a_1,b_1)+k_2(a_2,b_2)}{k_1+k_2}=\dfrac{(k_1+k_2)(a_1,b_1)-k_2(a_1, b_1)+k_2(a_2,b_2)}{k_1+k_2}=(a_1,b_1)-\dfrac{k_2[(a_1,b_1)-(a_2,b_2)]}{k_1+k_2}$
所以 $(A,B)$ 就是从 $(a_1,b_1)$ 出发到 $(a_2,b_2)$ 线段上的一点。
再加入 $(a_3,b_3)$ 进行配置，那就形成了以 $(a_1,b_1),(a_2,b_2)$ 为边界的三角形。
所以 $(a_1,b_1),(a_2,b_2)$ 和 $(a_1,b_1),(a_3,b_3)$ 和 $(a_2,b_2),(a_3,b_3)$ 共形成三条线段。能配成的药水就在这三条边形成的三角形内部，to_left 测试即可。
corner：
三角形有可能退化，即：$(a_1,b_1),(a_2,b_2),(a_3,b_3)$ 不一定能构成三角形。
- 三点相同，判断是否是点即可。
- 两点相同，判断是否在线段上即可。
- 三点共线，判断是否在最长的线段上即可。
总结：
先考虑小规模的，再考虑大规模的。
判断点在三角形内部，使用 to_left 测试容易实现。
expand：
若是给定 $n$ 种药水，也是一样的。区别在于 $n$ 种药水需要先求一个凸包，推导过程类似（对于三角形而言，其实是三个点形成的多边形一定是凸多边形）。
Cross on a Plane
题意简化：
在一个平面上，求可以覆盖所有点的十字丝带的最小宽度。
知识点：
点在直线上的投影。
解法：
引理1：两对边中至少有一对边都经过至少一个点。
容易发现，若两对边都有一条边没有经过任何点，那么可以将没有经过点的边逐渐向另一条边靠近，使得两对边中至少有一对边都经过至少一个点且答案更优。
引理2：对于两边都至少经过一个点的一对边，边之间的距离唯一确定了两边。
因为两点之间的距离是确定的，而两边之间的距离（也就是直角三角形的直角边）也是确定的，那么直角三角形的形态也就是确定的。
容易发现，答案的丝带长度是具有单调性的（当丝带长度超过真实答案长度时，一定还是有解的）
对于二分的每一个丝带长度，枚举一对边都经过至少一个点的两个点。此时，只要判断是否能用另一对边覆盖剩下的点即可。
考虑如何判断，剩下的点是不在枚举的一对边之间的点。
假设枚举的一对边的方向相同，那么不在这对边之间的点，在这一对边的同侧。
将这些剩下的点投影到枚举的一条边上，如果这些点的距离极差不超过当前二分的丝带长度则说明是可以全部覆盖的。
时间复杂度：$O(n^3\log t)$
总结：
通过 to_left 判断点在两条直线之间，实际上也是一种半平面交。