计算几何的基础知识

前置知识

$\pi$： 由于 $\arccos(-1) = \pi$，所以我们可以直接调用库中的函数 $acos(x)$ 直接求 $\arccos(x)$，因此 $\pi=acos(-1)$

余弦定理： 对于任意一个三角形，三条边分别是 $a,b,c$，$a$ 和 $b$ 的夹角为 $\theta$，则一定有 $c^2=a^2+b^2-2ab\cos\theta$

正弦定理： 对于任意一个三角形，三条边分别是 $a,b,c$，$b$ 和 $a$ 的夹角为 $\alpha$，$a$ 和 $c$ 的夹角为 $\beta$，$a$ 和 $b$ 的夹角为 $\theta$，则一定有 $\frac{a}{\sin\alpha}=\frac{b}{\sin\beta}=\frac{c}{\sin\theta}$

浮点数的比较

由于编程中我们存储浮点数的值都是存储一个近似数，假设我们存储 $a, b$ 为 $1.000000$，但是因为精度问题可能导致 $b$ 实际存储的值是 $1.000001$，此时我们判断 $a$ 和 $b$ 是否相同时，我们直接用 $a==b$ 判断就会得到否定的结果。因此如果我们想要判断两个浮点数是否相等，一般只要在一个规定的误差之内相等，我们就认为这两个浮点数相等。这里的误差一般规定为 $10^{-8},10^{-9},10^{-10}$ 都可以，并且不同的题目可能需要使用不同的误差才能过，这取决于出题人出数据时是用的多少误差。

这里引入两个常用的函数：

$sign(x)$ 表示符号函数，如果 $x$ 是正数就返回 $1$，如果 $x$ 是负数就返回 $-1$，如果 $x$ 是 $0$ 就返回 $0$。

const double eps = 1e-8; //误差
int sign(double x)
{
    if(fabs(x) < eps) return 0;
    if(x < 0) return -1;
    return 1;
}

$cmp(x,y)$ 表示比较函数，如果 $x=y$ 就返回 $0$，如果 $x \lt y$ 就返回 $-1$，如果 $x \gt y$ 就返回 $1$。

const double eps = 1e-8; //误差
int cmp(double x, double y)
{
    if(fabs(x - y) < eps) return 0;
    if(x < y) return -1;
    return 1;
}

向量

在坐标系上从某个点到另一个点的有向线段叫做向量。若从点 $(x_1,y_1)$ 到点 $(x_2,y_2)$，则这个向量就是 $(x_2-x_1,y_2-y_1)$

我们如果将任意一个向量的起点移到原点上，若终点坐标为 $(x,y)$，则此时向量刚好也是 $(x,y)$。接下来我们用 $(x,y)$ 表示从原点到点 $(x,y)$ 的向量，我们也可以记作 $\vec{a},\vec{b},\vec{c}$ 等等。

向量加法： 若 $\vec{a}$ 为 $(x_1,y_1)$，$\vec{b}$ 为 $(x_2,y_2)$，则 $\vec{a}+\vec{b}$ 就是 $(x_1+x_2,y_1+y_2)$。$\vec{a}+\vec{b}$ 其实就是从 $\vec{a}$ 的终点再走一个 $\vec{b}$ 到达的点所表示的向量。从几何意义上看，$\vec{a}+\vec{b}$ 就是 $\vec{a}$ 和 $\vec{b}$ 构成的平行四边形的对角线。

向量减法： 若 $\vec{a}$ 为 $(x_1,y_1)$，$\vec{b}$ 为 $(x_2,y_2)$，则 $\vec{a}-\vec{b}$ 就是 $(x_1-x_2,y_1-y_2)$。从几何意义上看， $\vec{a}-\vec{b}$ 其实就是 $\vec{ba}$，这可以用向量加法反推得出，不再赘述。

向量数乘： 若 $\vec{a}$ 为 $(x,y)$，我们令 $\vec{a}$ 乘上一个常数 $b$，称为向量的数乘，而 $b~\vec{a}$ 就是 $(bx,by)$，从几何意义上看，数乘就是用来改变向量的大小的。

模长： 一个向量的模长就是它的长度，记作 $\vert \vec{a} \vert$，如果 $\vec{a}$ 为 $(x,y)$，则 $\vert \vec{a} \vert = \sqrt{x^2+y^2}$

内积（点积）： 若 $\vec{a}$ 为 $(x_1,y_1)$，$\vec{b}$ 为 $(x_2,y_2)$，$\vec{a}$ 和 $\vec{b}$ 的点积也就是 $\vec{a} \cdot \vec{b} = x_1\cdot x_2+y_1 \cdot y_2$，这是代数上的定义。而在几何上的定义，$\vec{a} \cdot \vec{b}=\vert \vec{a} \vert \vert \vec{b} \vert \cos{\theta}$，其中 $\theta$ 表示从 $\vec{a}$ 逆时针旋转到 $\vec{b}$ 的角度。其实就是 $\vec{b}$ 到 $\vec{a}$ 的投影再乘上 $\vec{a}$ 的模长，反过来也一样。代数定义和几何定义是等价的。

代数定义的代码实现：

struct Point
{
    double x, y;
}; //向量

double dot(Point a, Point b) //点积
{
    return a.x * b.x + a.y * b.y;
}

在代码实现中，我们一般用代数定义来求点积，因为几何定义中涉及到了开方运算和三角函数运算，而三角函数中又需要进行除法运算的，而在编程中除法运算、三角函数运算、开方运算的精度都是相对较低的，且运行效率较慢，因此我们应该尽可能使用加法和乘法，精度又高，速度又快。

外积（叉积）： 若 $\vec{a}$ 为 $(x_1,y_1)$，$\vec{b}$ 为 $(x_2,y_2)$，$\vec{a}$ 和 $\vec{b}$ 的点积也就是 $\vec{a} \times \vec{b} = x_1\cdot y_2-x_2 \cdot y_1$，这是代数上的定义。而在几何上的定义，$\vec{a} \times \vec{b} = \vec{a} \cdot \vec{b}=\vert \vec{a} \vert \vert \vec{b} \vert \sin{\theta}$，其中 $\theta$ 表示从 $\vec{a}$ 逆时针旋转到 $\vec{b}$ 的角度。其实就是 $\vec{a}$ 和 $\vec{b}$ 构成的平行四边形的面积（该平行四边形的面积是有向面积，如果 $\theta$ 是从 $\vec{a}$ 顺时针旋转到 $\vec{b}$ 的话，这个平行四边形的面积就是负的。）。

代数定义的代码实现：

struct Point
{
    double x, y;
}; //向量

double cross(Point a, Point b) //点积
{
    return a.x * b.y - b.x * a.y;
}

而叉积为了效率和精度同样使用代数定义来求。

向量的常用操作

注意，为了效率和精度能尽可能的高，以下函数都尽可能使用加法和乘法来实现。

struct Point
{
    double x, y;
}; //向量

double get_length(Point a) //求一个向量的模长（长度）
{
    return sqrt(cdot(a, a));
}

double get_angle(Point a, Point b) //求两个向量的夹角
{
    return acos(dot(a, b) / get_length(a) / get_length(b));
}

double area(Point a, Point b, Point c) //求向量 ab 和向量 ac 构成的平行四边形的有向面积
{
    return cross(b - a, c - a);
}

double rotate(Point a, double angle) //求出将向量 a 顺时针旋转 angle 弧度后的向量
{
    return Point(a.x * cos(angle) + a.y * sin(angle), -a.x * sin(angle) + a.y * cos(angle));
}

点与线

直线定理：

一般式：$ax+by+c=0$
点向式：$p+t~\vec{v}$（$p$ 是一个点，点向式即用直线上的一个点和一个方向表示直线）
斜截式：$y=kx+b$

点与线的常用操作

判断点 $a$ 在直线上：取直线上任意非零向量 $\vec{v}$，取直线上一点 $b$，如果 $\vec{ba} \times \vec{v} = 0$，则点 $a$ 在直线上。

//cross(v, w) == 0，则两直线平行或重合
Point get_line_intersection(Point p, vector v, Point q, vector w) //求两个点向式直线（p+tv 和 q+tw）的交点
{
    vector u = p - q;
    double t = cross(w, u) / cross(v, w);
    return p + t * v;
}

double distance_to_line(Point p, Point a, Point b) //求点 p 到直线 ab 的距离
{
    vector v1 = b - a, v2 = p - a;
    return fabs(v1, v2) / get_length(v1);
}

double distance_to_segment(Point p, Point a, Point b) //求点 p 到线段 ab 的距离
{
    if(a == b) return get_length(p - a);
    vector v1 = b - a, v2 = p - a, v3 = p - b;
    if(sign(dot(v1, v2)) < 0) return get_length(v2);
    if(sign(dot(v1, v3)) > 0) return get_length(v3);
    return distance_to_line(p, a, b);
}

double get_line_projection(Point p, Point a, Point b) //求点 p 在直线 ab 上的投影
{
    vector v = b - a;
    return a + v * (dot(p - a, v) / dot(v, v));
}

bool on_segment(Point p, Point a, Point b) //判断点 p 是否在直线 ab 上
{
    return sign(cross(p - a, p - b) == 0) && sign(cross(p - a, p - b)) >= 0;
}

bool segment_intersaction(Point a1, Point a2, Point b1, Point b2) //判断线段 a1a2 和线段 b1b2 是否相交
{
    double c1 = cross(a2 - a1, b1 - a1), c2 = cross(a2 - a1, b2 - a1);
    double c3 = cross(b2 - b1, a2 - b1), c4 = cross(b2 - b1, a1 - b1);
    return sign(c1) * sign(c2) <= 0 && sign(c3 * sign(c4) <= 0);
}

三角形

求三角形面积：

如果给出三个顶点的坐标，则可以用叉积来求面积。

如果给出三条边的边长 $a,b,c$，则设 $p=\frac{a+b+c}{2}$，则面积 $S=\sqrt{p(p-a)(p-b)(p-c)}$

求三角形的四个心：

1. 外心（外接圆的圆心），外心就是三条边中垂线的交点，外心到三个顶点的距离相等
2. 内心（内切圆的圆心），内心就是三条角平分线的交点，内心到三条边的距离相等
3. 垂心，垂心就是三个顶点到其对边的垂线的交点
4. 重心，三个顶点分别向其对边中点连线，三条线的交点就是重心，重心是三个顶点距离的平方和最小的点，也是到三条边距离乘积最大的点。

普通多边形

对于任意多边形，我们通常按照逆时针将所有点存储起来。

多边形的定义： 由在同一平面且不再同一直线上的多条线段首尾顺次连接且不相交所组成的图形叫多边形。

普通多边形的定义： 简单多边形就是除相邻边外其他边不相交的多边形。

凸多边形： 过多边形的任意一边做一条直线，如果其他各个顶点都在这条直线的同侧，则把这个多边形叫做凸多边形。任意凸多边形外角和为 $360^。$，任意凸多边形内角和为 $(n-2)180^。$

普通多边形的常用操作

求多边形的面积（不一定是凸多边形）： 我们先任意一个点 $p$，然后逆时针或顺时针方向枚举所有边，对于每条边 $(u,v)$，求一下 $\vec{pu}$ 和 $\vec{pv}$ 构成的三角形的面积，累加所有三角形的面积的绝对值就是多边形的面积。这里的 $p$ 为了方便可以直接取多边形的第一个顶点。

double polygon_area(Point p[], int n) //求多边形的面积
{
    double s = 0;
    for(int i = 1; i + 1 < n; i++)
        s += cross(p[i] - p[0], p[i + 1] - p[i]);
    return s / 2;
}

判断某一个点 $p$ 是否在多边形内（不一定是凸多边形）：

1. 射线法，从 $p$ 出发向随机方向射出一条射线，不要和多边形的任意边重合，如果这条射线和多边形的奇数条边相交，则 $p$ 一定在多边形内，如果和多边形的偶数条边相交，则 $p$ 一定在多边形外。

2. 转角法，从逆时针或顺时针方向枚举所有边，对于每条边 $(u,v)$，计算一下 $\vec{pu}$ 和 $\vec{pv}$ 构成的夹角的度数，如果点 $p$ 在多边形内部，则所有夹角的度数和就是 $360^。$，如果在多边形外，则所有夹角的度数和是 $0^。$

判断某一个点 $p$ 是否在凸多边形内：

逆时针方向枚举所有边，如果 $p$ 在凸多边形内，则 $p$ 一定在每条边的左侧。

皮克定理

若一个多边形的所有顶点都在整数点上，则该多边形的面积 $S=a+\frac{b}{2}-1$，其中 $a$ 表示多边形内部的整数点个数，$b$ 表示多边形的所有边上的整数点个数。

圆

圆与直线的交点

两圆交点

点到圆的切线

两圆的公切线

两圆相交的面积

以上五个是和圆相关的操作，而这些操作都是需要现场联立方程来求解的，而求两圆相交的面积是还需要做一下辅助线，这里就不过多讲解了，会在相关题目中再做讲解。

注意，以上我们是用结构体来存储每个点的坐标，以上的代码实现中的存在一些点与点的加减法运算，因此还需要对结构体重载一下运算符，当然也可以用 $pair$ 来存储每个点的坐标，可以根据个人习惯而定。