计算几何

计算几何是一个偏冷门的板块（基本只有 SCOI 考/gg），但是基本的了解还是要有的。
平面几何基础

向量与点

由于点和向量的运算和性质等的相似性，我们将其一并定义。
定义向量与点

\[\vec a=\{ x,y\},A=\{ x,y\}\]
注意到二者有类似的形式。事实上，我们经常将二者视为同一种东西，因此经常直接将点代做向量进行向量运算。例如点 \(A\)，我们可以直接将其视作 \(\vec A\) 带入运算。
向量的基本运算分为向量与实数运算和向量间运算。
其中，向量间运算主要分为叉积和点积两种。

\[\begin{aligned}\vec a\times \vec b &=x_ay_b-y_ax_b \\\vec a \cdot  \vec b &=x_ax_b+y_ay_b\end{aligned}\]
叉积的几何意义为 \(\vec a\) 与 \(\vec b\) 之间夹成的三角形的面积的两倍，点积的几何意义是一个向量在另一个向量上的投影长度。
若 \(\vec b\) 在 \(\vec a\) 的逆时针方向，叉积为正，反之为负，共线为 0。这一个性质相对关键，比较常用。
而如果两个向量的夹角为钝角，则点积为负，反之为正，恰好垂直则为 0。
在旋转之前，我们先介绍极角。极角是指 \(x\) 轴正半轴与向量逆时针方向夹成的角。这个还是比较好理解的。
向量的旋转可以通过和角公式推导。设旋转角度为 \(\theta\)，\(\vec a\) 的长度为 \(r\)，极角为 \(\varphi\)，有

\[\begin{aligned}\vec a &=\{x=r\cos \varphi,y=r\sin \varphi\}\\\vec {a'} &=\{x'=r\cos \varphi +\theta,y'=r\sin \varphi+\theta\}\\x' &= x \cos \theta - y \sin \theta \\y' &= x \sin \theta + y \cos \theta\end{aligned}\]
这就是向量的旋转公式，还比较好推。
直线

由于可能存在竖直的线，因此直线与线段一般都不使用斜率来存，而是用线上的两个点来确定线的形态。
同时，由于计算几何的特殊性，我们是要求直线与线段是有方向性的，其方向的规定与向量类似。
定义一条直线被点 \(s,t\) 确定，方向是 \(s\to t\)。
点 \(B\) 到直线的距离 \(L\) 可以通过常见的面积法得到。由于叉积的几何意义，我们直接有

\[L=\frac{|\vec{Bs} \times \vec{Bt} |}{dis_{s,t}}\]
其中 \(dis_{u,v}\) 表示两点间的距离。
直线交点由相似法得到。假设第一条直线的起终点分别为 \(A,B\)，第二条的为 \(C,D\)，设原点为 \(O'\)，交点为 \(O\)，则

\[\vec{O'O} = \vec{O'A} + \frac{\vec{AC} \times \vec{CD}}{\vec{AB} \times \vec{CD}} \vec{AB}\]
其中分子上是 \(\triangle ADC\) 面积的两倍，分母是四边形 \(ACBD\) 的面积。这个分数相当于是求出了 \(\frac{AO'}{AB}\) 的值。
一个点 \(A\) 向一条直线作垂线的垂足，实际上就是投影向量，可以通过点积快速得到。
设垂足为 \(O\)，有

\[O=\frac{(\vec A-\vec s)\cdot \vec{st}}{|\vec {st}|^2}\vec {st}+\vec A\]
线段

基本与直线类似。需要注意的是对于线段而言，一个点到线段的距离与直线是不同的。
如果一个点不在线段“对应”的平面内，那么距离就不是直线，而是到最近的端点的距离。所谓“对应”就是指是否这个点与两个端点的两条连线与线段本身的夹角都小于等于九十度。这个东西可以用点积的性质快速判。
多边形

一般我们存储多边形的方式都是通过点集。存储的相邻两个点之间存在连边，最后一个点与第一个点连边，所有边组成一个封闭图形。
简洁起见，我们定义第 \(i\) 个点在多边形上的下一个点为 \(nxt (i)\)，这主要是为了方便最后一个点与第一个点间连边的表示。
在代码实现中，由于使用了 vector 存储，因此点的编号是从 0 开始的。而在算式中，我们为了方便从 1 开始编号。一般将多边形的点积设为 \(P\)，多边形上的第 \(i\) 个点表示为 \(P_i\)，一共有 \(n\) 个点。
我们在这里约定一般的多边形都是点逆时针旋转的方向存储的。
多边形的周长是好算的，直接将两个相邻点的距离加起来即可。
多边形的面积则是一个相对困难的点。由于没有保证多边形是一个凸多边形，因此我们不能采用类似将多边形分成若干个三角形的方式快速计算。我们希望能有一个简洁的公式能够快速计算。事实上，我们有

\[S=\frac 1 2\sum_{i=1}^n\vec{P_i}\times \vec{P_{nxt_i}}\]
确实比较简洁，但证明并不显然。对于凸多边形，这个公式还是相对显然的。讨论原点在多边形内部与外部两种情况，可以通过画图比较明显的得出来。
而对于凹多边形，情况就变得复杂了起来。画个图可以发现，由于叉积自带符号的特性，这个式子容斥的意味变得比较深。

其中红色的是负，蓝色的是正。在感性上可能能理解，在理性上感觉不严谨。
<blockquote>叉积性质

\(1\over2\) 叉积即带符号的三角形面积，多边形每条边对应的面积为正/负，称之为 \(+1\) 边 / \(-1\) 边。

对于边 \(AB\)（\(A=A_i,B=A_{(i+1)\bmod n}\)），引射线 \(OA\)，看 \(AB\) 相对于 \(A\) 之后的射线是顺时针还是逆时针转（转动 \(>x>>y;}                void put(){cout