基础知识
（本篇以简短的语言只讲代码中常用的，如果后面做题有新的自然会补，想深入了解？）。
前置：1.向量是可以用一个坐标表示的。
2.向量减：a⃗\vec aa −-− b⃗\vec bb===(xa−xb，ya−yb)(x_a-x_b，y_a-y_b)(xa −xb ，ya −yb )。
3.向量数乘：a⃗\vec aa ∗*∗ kkk=(xa∗k，ya∗k)=(x_a*k，y_a*k)=(xa ∗k，ya ∗k) k∈Rk \in Rk∈R。
4.向量模长：∣AB→∣| \overrightarrow {AB} |∣AB∣ === dis(AB)dis(AB)dis(AB)。
考虑一个有方向有大小的a⃗\vec aa，有两个点A(x1，y1)A(x1，y1)A(x1，y1)，B(x2，y2)B(x2，y2)B(x2，y2)固定这个向量，方向AAA到BBB，在代码里我们用B−AB-AB−A表示a⃗\vec aa。
（注：夹角为 θ\thetaθ）
考虑点乘a⃗\vec aa ⋅\cdot⋅ b⃗\vec bb === ∣a∣|a|∣a∣ ∗*∗ ∣b∣|b|∣b∣ ∗*∗ cosθcos \thetacosθ，代表a⃗\vec aa 在 b⃗\vec bb 上的投影长度再乘上∣b⃗∣| \vec b |∣b∣。
坐标表示：dot(a⃗，b⃗)dot(\vec a，\vec b)dot(a，b) === xa∗xb+ya∗ybx_a*x_b+y_a*y_bxa ∗xb +ya ∗yb 。
考虑叉乘a⃗\vec aa ×\times× b⃗\vec bb === ∣a⃗∣| \vec a |∣a∣ ∗*∗ ∣b⃗∣| \vec b |∣b∣ ∗*∗ sinθsin \thetasinθ 表示以a⃗\vec aa，b⃗\vec bb 为底边的平行四边形面积
（看了那么多图应该可以自己画了吧？）
坐标表示：cross(a⃗，b⃗)cross(\vec a，\vec b)cross(a，b) === xa∗yb−ya∗xbx_a*y_b-y_a*x_bxa ∗yb −ya ∗xb 。
还有很多点，线的关系（我们暂且不考虑三维，反正我不会），需要向某位大佬自学再食用。
应用专题
一个点是否在任意多边形内：
数学上我们取一条与所有多边形边不平行的射线，这个射线从这个点出发与多边形相交的边数，奇内偶外
代码中我们取一个+∞，+∞+\infty，+\infty+∞，+∞的点（通常可以为10910^9109）与这个点构成一个线段，再用线段是否相交的方法解决就行。当然有1109\frac {1}{10^9}1091 的概率会导致挂掉（可以想一想为什么？），但概率极小一般不会错。
例题：HDU-1756 CUPID'S ARROW
障碍物最短距离问题
考虑在一个二维平面上有两个点AAA，BBB，有一个圆，问两点之间不经过圆的最短距离。
如图：
如AAA，BBB，当最短距离不经过圆时则直接输出答案；
再考虑CCC，DDD情况，显然找切点再走一段劣弧是最短距离
Ans=min(CF+FG⌢+GD，CH+HI⌢+DI)Ans=min(CF+\overset{\frown}{FG}+GD，CH+\overset{\frown}{HI}+DI)Ans=min(CF+FG⌢+GD，CH+HI⌢+DI)
例题：INTERSTELLAR … FANTASY GYM - 102056F
乍一看是三维问题，但是我们注意到AAA，BBB与圆心OOO三点构成一个平面，可以转化为二维来做。
当然一些角度问题得仔细思考
INTERESTED IN SKIING
一道非常神秘综合的计算几何，思维含量还是蛮高的。
对于这么一道题，直接看 Kotori 是否能穿过会非常复杂，但是我们可以换一个角度看问题：障碍物将 Kotori 拦住的小代价是什么？我们成为了拦截 Kotori 的人。
什么时候障碍物会将 Kotori 拦住？相当于左边界（定义为 000 节点）和右边界（定义为 n+1n+1n+1 节点）是连通的。
换句话说，我们（你也可以认为障碍物们）可以定义代价 wi,jw_{i,j}wi,j 为在 iii 障碍物与 jjj 障碍物（把它们看做 iii 和 jjj 节点）连一条边，那么根据木桶原理，拦截能力取决于最小的地方，而障碍物会让这个值尽可能大，穿过这个 nnn 个节点的答案是个最大的最小路径，这个我们可以用一个 Dijsktra 解决，在所有路径中让其中最小值尽可能大！
上面的有点绕，细细评鉴一下。
这样我们把二维平面问题转化为图论，接着就是考虑代价。
根据题目要求的，代价 wi,jw_{i,j}wi,j 就是只考虑穿过 iii 和 jjj 节点所需的最大 vxv_xvx ，因为要。考虑到我们可以枚举端点（因为极限情况下端点一定取到最小），接着按题意计算即可：
wi,j=Δxt通过=ΔxΔyvy=vy×ΔxΔyw_{i,j}= \frac {\Delta x}{t_{通过}}=\frac{\Delta x}{\frac {\Delta y}{v_y}}=v_y \times \frac {\Delta x}{\Delta y}wi,j =t通过 Δx =vy Δy Δx =vy ×ΔyΔx
但我们要考虑特殊情况：
1. 绝对的死路：两个障碍物 yyy 有交集，但本该在左边的障碍物其 xxx 值大于右侧，说明被严格封死，代价 +∞+ \infty+∞。
2. 枚举端点时，若 yyy 相等则无意义跳过。
3. 如果 y1≠y2y1\not =y2y1=y2，那么如果 x1<x2x1<x2x1<x2，则中间有空隙，可以直接穿过去，所以代价中应该是 max(0,Δx)\max (0,\Delta x)max(0,Δx)。
这样我们就做完了：
感觉非常巧妙！！
凸包专题
经典问题：考虑任意几个点，求最小凸包。
一般我们用的是AndrewAndrewAndrew算法，按照x，yx，yx，y排序，以便我们向量处理。
接着用一个栈去存处理的节点，当新加入一个节点时，考虑栈顶上两个点是否与这个点构成凸包，如果可以就入栈反之弹出栈顶，直到能构成。
（如图，当前处理完kkk个节点，考虑加入第k+1k+1k+1个节点）
若(k−1)k→\overrightarrow {(k-1)k}(k−1)k ×\times× (k−1)(k+1)→\overrightarrow{(k-1)(k+1)}(k−1)(k+1) ≤0\le 0≤0 则不合法，
反之合法
特别的，等于0时一定要弹出，因为这个点是在凸包上而不是顶点
实现部分我个人比较喜欢分上凸壳，下凸壳处理。
代码（以模板题求周长为例子）
时间复杂度O(nlogn)O(n \log n)O(nlogn)
考虑进阶问题：如何快速求一个点SSS是否在凸包内
subtask1：O(n)O(n)O(n)，显然是简单的，对于每条线段和这个点判断一下位置，如果都在同侧则在内部
subtask2：O(logn)O(\log n)O(logn)，考虑固定一个凸包顶点，我习惯固定xxx最小，yyy最小的点，记为XXX，对其他点按照与XXX的极角从小到大排序（若极角相等则按照与X距离从小到大）。
当然这种方法也是求凸包的一种（GramhamGramhamGramham），判断条件也是一样的，待会补。
回归正题，这么做完之后，再对SSS与XXX求一遍极角。
结合图
考虑二分，最后会缩小到只包含一个线段的区间
若u→\overrightarrow {u}u ×\times× ls→\overrightarrow{ls}ls ≥0\ge 0≥0 则合法，反之不合法
这样我们就在O(logn)O(\log n)O(logn)求出一个点是否在凸包内了
先补一个GrahamGrahamGraham模板题的代码：
POLYGONS CODEFORCES - 166B
进阶问题的板子，如果一个多边形在凸包内，则这个多边形每个点一定在凸包内。观察数据范围，显然O(nm)O(nm)O(nm)是无法接受的，所以用进阶问题思路即可做到O(mlogn)O(m \log n)O(mlogn)。
实现时注意是顺时针读入，把每个问题想清楚
THE SUPERSONIC ROCKET CODEFORCES - 1017E
再考虑一个凸包结合KMPKMPKMP问题：
题目概述：给定两串点先求凸包，再判断两个凸包是否同构。
求凸包很简单，上面讲过了。那怎么判同构呢？（想了很久......
回归最初，考虑一个多边形的特征：边，角。那我们判断两个是否同构，就相当于判多边形的特征是否相同。
我们用一个结构体存对于一个点iii，到下个点i+1i+1i+1的长度平方，关联两边的叉乘和点乘（反应这个角的sinsinsin和coscoscos）
这样我们把二维凸包压成一个一维序列，接下来怎么做？
考虑到两个序列开始位置不同，相当于判断两个序列循环位移是否相同？这个就非常板子了，复制两份跑KMPKMPKMP即可。
这样我们又做完了一个紫题！
鬼知道我调了多久，没招了。。@cjdst怎么WA了
当然还有旋转卡壳，开个坑，学会了再补。。。
