文章总览：雪地的圣女

计算几何，好像是非常难的一部分……其实还是数学，说着难，其实也还好（好罢我不会）。总而言之，这篇文章来简单介绍一下最最基础的计算几何，下为本文大纲：

  1. 向量的定义
  2. 向量的运算
  3. 直线表示法
  4. 直线的运算
  5. 凸包的定义
  6. 凸包的运算
  7. 半平面定义
  8. 半平面模板
  9. 几何大模板
  10. 几何例题一
  11. 几何例题二

前置知识：付记忆入殓

定义：悲鸣，赐死之先声

首先定义向量，其实向量在以前的文章也接触过，不过比较基础，而且并没有给出详细的定义，所以说我们还是先说一个较为形式化的定义。

友情链接：

【算法介绍】快速傅里叶变换 - 复数及其运算 | 祝馀宫

向量，顾名思义就是有方向的量，在数学上来说，只要不改变向量的大小和方向，其端点是可以随意再平面中移动的，一般记作 $\vec a$ 。事实上，向量可以认为是一个有向的线段，而有向线段的三要素非常相似于力的三要素，即起点、方向、长度。所谓三要素，就是只要知道了这三个信息，剩下的信息就可以唯一确定，所以我们也用有向线段来表示向量。

除此之外，向量还有一些其他的概念。

  • 向量的模长：就是向量的长度，记作 $|a|$；
  • 零向量：模长为 $0$ 的向量，零向量的方向是任意的，记作 $\vec 0$ ；
  • 单位向量：模长为 $1$ 的向量称为该方向的单位向量，记作 $\vec e\ $；
  • 平行向量：方向相同或者相反的两个非零向量，记作 $a\parallel b$ ；
  • 相等向量：除了起点以外的两个要素相等的向量；
  • 相反向量：模长相等，方向相反的两个向量；
  • 向量的夹角：对于两个非零向量 $\vec a,\vec b\ $，分别作 $\overrightarrow {OA},\overrightarrow{OB}$，则设 $\theta$ 等于劣角 $\angle AOB$，此时 $\theta$ 称为向量 $\vec a, \vec b\ $的夹角，记作 $\langle\vec a,\vec b\rangle$。当 $\theta= 0$ 时两向量同向，$\theta=\pi$ 时两向量反向，$\theta=\frac{\pi}{2}$ 两向量垂直。

另外，具有方向的向量不可以比较大小，但是可以相等。

运算：哀悼，死海之涟漪

向量运算，无非就是加减乘除一类的了，但首先的话，我们要先来看看，向量的表示法。

表示法

由于向量是可以平移的，所以我们不妨将向量的端点全部移动到原点，这样就可以用表示点的方式来表示向量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct Point;
typedef Point Vector;
struct Point {
	double x, y;
	Point(double x = 0, double y = 0) : x(x), y(y) {}
    inline double vlen() {
        return sqrt(x * x + y * y);
    }
    // 由于向量和点用了同一个结构体，= 向量也能用，但是 < 向量用不了
    // （其实你想用也行，不过不是数学意义上的比大小了）
    inline bool operator == (const Point &a) const {
        return sgn(x - a.x) == 0 && sgn(y - a.y) == 0;
    }
    inline bool operator < (const Point &a) const {
        return sgn(x - a.x) < 0 ¦¦ sgn(x - a.x) == 0 && sgn(y - a.y) < 0;
    }
};

加减法

向量的加减和我们在物理课上学到的力的加减是一样的，简单来说有两种：

分别就是三角形法则和平行四边形法则，但是本质上来讲，这两种法则其实是一样的。从代码的角度来说，不管怎么样，最终的答案向量都是这两个向量的 $x,y$ 参数分别相加。

那么很显然，这样的加法显然满足交换律和结合律，并且减法也是同理的。

1
2
3
4
5
6
inline Vector operator + (const Vector &a) const {
        return Vector(x + a.x, y + a.y);
}
inline Vector operator - (const Vector &a) const {
        return Vector(x - a.x, y - a.y);
}

数乘法

数乘说白了就是对于一个向量进行缩放特定倍数，没什么好说的。

1
2
3
4
5
6
inline Vector operator * (double t) const {
        return Vector(x * t, y * t);
}
inline Vector operator / (double t) {
        return Vector(x / t, y / t);
}

点乘法

然后是关于向量的乘法了，向量主要有两类乘法，点乘和叉乘，我们先讲相对简单的点乘。

点乘的话是比较基础的乘法，这个运算是两个向量做点乘以后返回了一个标量，所以也被叫做点积、内积等等等等名称。那么首先给出点乘的定义：

观察这个式子不难发现。$|\vec b|\cos\left(\langle\vec a,\vec b\rangle\right)$ 其实就是向量 $b$ 在向量 $a$ 上的投影。有了这个概念，我们可以用这个式子的变式得到很多奇奇怪怪的信息：

  1. 向量的模长：$|\vec a| = \sqrt{\vec a\cdot \vec a}$
  2. 向量的夹角：$\theta=\arccos\frac{\vec a\cdot\vec b}{|\vec a||\vec b|}$

另外关于这个式子的化简，有一个简单的计算公式：

这个式子的推导其实就是三角恒等变换，简单的带入一下对应的数据就能算出来。

1
2
3
inline double dot(const Vector &a) {
        return x * a.x + y * a.y;
}

另外由于点乘的结构，点乘是满足交换律和分配律的。且对于向量的放缩，也满足结合律，可以用如下的式子表示。

  1. $a\cdot b = b\cdot a$
  2. $a\cdot(b + c) = a\cdot b+a\cdot c$
  3. $\lambda a\cdot b=\lambda(a\cdot b)$

这个性质倒是挺好的，这种都属于非常有用的了。

叉乘法

叉乘其实是三维向量的一个特有运算。但为什么放在二维向量里面讲呢？这是因为在二维向量中也存在类似的效果，所以说我们把叉乘从三维向量推广到二维向量中。

首先给出叉乘的概念：叉乘，也称叉积，是两个三维向量的运算，运算结果如下：

  • $|\vec a\times \vec b|=|\vec a||\vec b|\sin\langle\vec a, \vec b\rangle$。
  • $\vec a \times \vec b\ $与 $\vec a,\vec b\ $都垂直，且符合右手法则。

*右手法则是一个玄学的东西，大体上是通过右手手势来判断向量方向，可以自己查一下

那么为什么说这个东西可以拓展到二维向量呢？我们对于两个二维向量 $\vec a(x_a,y_a)$ 和 $\vec b(x_b, y_b)$，二维其实之比三维少一个 $z$ 轴，所以说我们额外添加一个轴，变为 $\vec a(x_a,y_a,0)$ 和 $\vec b(x_b,y_b,0)$，由于他们都是在由 $x,y$ 轴构成的平面上的，想要垂直于他们很简单，其实就是平行于 $z$ 轴上的一段向量，答案即为 $\vec a\times \vec b=(0,0,|\vec a||\vec b|\sin\langle\vec a,\vec b\rangle)$。

但是这个式子还是太玄学了，有没有更加简单的计算方式呢？有的兄弟有的。如果我们把这两个三维向量写成下面这样，我们可以得到这样一个行列式。

这里的 $\vec i, \vec j,\vec k$ 分别表示空间中方向为 $x,y,z$ 轴正方向的三个单位向量，运用亿点点的常识就可以知道，可以计算出这个向量是：$\vec c = (0,0,x_ay_b-y_ax_b)$。

1
2
3
inline double operator * (const Vector &a) const {
        return x * a.y - y * a.x;
}

另外也再提一嘴叉乘的性质，首先，差乘也有分配律和对于数乘的结合律。但是与点乘不同的是，叉乘不具有交换律，这个观察式子也可以得出来，如果硬要交换，需要交换后取叉乘结果数乘上 $-1$，即 $\vec a\times \vec b = -\vec b\times \vec a$ 。

旋转法

最后就是向量的旋转。

对于一个向量 $\vec a(x,y)$ 我们定义它的 $l$ 就是模长 $l=\sqrt{x^2+y^2}$，然后我们让它逆时针旋转 $\alpha$ 度。

然后就又是快乐的三角恒等变换环节：

最后就是用了亿点点的三角函数把 $x, y$ 分别代入回去罢了。

另外还有一个特殊情况，就是做一个逆时针旋转 $90^\circ$ 的向量，我们称之为法向量，在做垂直的时候很需要，所以说我们单独开了一个函数来算。

1
2
3
4
5
6
inline Vector rotate(double ang) {
    return Vector(x * cos(ang) - y * sin(ang), x * sin(ang) + y * cos(ang));
}
inline Vector norm() {
        return Point(-y, x);
}

初阶应用：以繁花加冕

表示：缄默，幽蝶之轻抚

接下来来看向量，或者上上面这个类的一些初级运用罢。我们知道，两点确定一直线，所以说我们对于直线或者线段的表示方法，其实都应该和两个点有关。如果我们用两个点表示了线段，那么直线有应该如何表示呢？

直线是直线，两端可以无限延长，这就导致了两点在来表示显得有一些缺陷。所以呢，不难想到我们在平面直角坐标系最最常见的直线，一次函数。如果我们用一次函数的形式来表达，其实就是记录每一项的参数。记录一个函数的话，形式仍有漏洞，我们可以拓展一下，把函数表达式变为 $ax+by+c$，这样也是一次函数，不过更加易于处理。

那么给出线段与直线的两个类：

1
2
3
4
5
6
7
8
9
// 虽说是线段，但是在需要用到直线上的点时也做直线
struct Seg { 
    Point s, e;
    Seg() {}
    Seg(Point s, Point e): s(s), e(e) {}
};
struct Line {
    int a, b, c;
};

这个类表示的就是我们上面的意思，接下来又是关于直线和线段的一些奇奇怪怪的应用。

运算：怒哮，苏生之颂铃

既然有点和直线的区别，那么自然代码也要分两类。

三点位置关系

三个点的位置关系其实很好判断，我们需要用到叉乘的一个性质：两个向量的叉乘是他们所构成的三角形面积的一半。这个是可以证明的，看下图：

叉乘面积

由这个图形也不难看出，确实是黄色的三角形也即是两个向量所围成的图形都可以分别转化为三个小矩形的一半，而这三个小矩形的面积刚好就是叉乘的结果即 $x_ay_b-x_by_a$，至此也算是感性的把这个证明完了。

有了这个性质，我们如何来判断三点位置关系其实也就简单了。比如说我们要求 $A,B,C$ 三个点的位置关系，可以分别作出向量 $AB,AC$，然后求叉积，这时候叉积会有下面几种可能：

  1. 正：$C$ 在直线 $AB$ 左侧；
  2. 零：$A,B,C$ 三点共线；
  3. 负：$C$ 在直线 $AB$ 右侧；
1
2
3
double cross(Point a, Point b, Point c) {
	return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}

能判断左右是因为叉积是个差值，所以可能会有正负之分，自己花一张图就可以看出来了。虽然说是判断三点位置关系，但是同样的不难主要主要判断的是直线 $AB$ 的两侧，所以说这个同样也是判断点与线的位置关系的函数。

两条线的交点

两条线的交点，其实也分两种，直线与直线或者线段与线段。首先如果要求交点的话，首先要判断是否相交。那么从最简单的直线开始考虑，直线因为可以无限延长，所以只要不是平行或者共线，就一定会有唯一确定的交点。那么直线相交怎么求呢？很困难，如果用一次函数的形式。

所以我们不难想到在直线上取两个点做向量，如果这两个向量的叉乘是 $0$ 那么说明平行或者共线，这样就是完成了基础部分，判断是否相交。那么已经确定了相交，如何求交点呢？如果用一次函数的形式，同样很麻烦。倒不是说不行，是真的麻烦，解方程，太烦了。

那么曾经百试不爽的向量还有没有用呢？有的。首先因为向量是可以随意平移的，所以说在表述直线或者线段的时候，我们都需要一个定点来描述起点，这样直线就跑不掉。然后就是向量魅力时刻，先上图。

看到这图你肯定会一头雾水，那么不得不提一下上面提到的叉积性质的拓展了。因为说过两个向量的叉积其实等于这两个向量所围成的三角形面积的一倍，所以换一个说法，我们也可以认为叉积是以这两个向量为临边所构成的平行四边形的面积。

我们现在有直线 $AB,CD$，我们分别以 $B,D$ 为起点做向量 $\overrightarrow{AB},\overrightarrow{CD}$。这时候我们先用起点连线 $BD$ 与 $AB$ 做叉乘，得到了平行四边形 $ABDE$。然后再用 $AB$ 与 $CD$ 做叉乘，得到的值其实等价于平行四边形 $CDEF$ 的面积。这时候由于两个平行四边形同底，他们的面积之比就是高的比值，自然可以以这个比值得到交点 $O$ 的位置。

1
2
3
4
5
6
7
bool intersect(Point P, Vector v, Point Q, Vector w, Point &ret) {
        Vector u = P - Q;
        if(sgn(v * w) == 0) return false;
        double t = w * u / (v * w);
        ret = P + v * t;
        return true;
}

那么有了这个东西，接下来也好处理。不论是直线与直线相交，还是线段与直线相交，还是线段与线段相交。本质都是线相交，不过线段有了范围限制而已，所以说我们可以直接先求直线交点，然后再来判断交点是否在线段上即可。

1
2
3
4
5
bool intersect(Seg a, Point Q, Vector w, Point &ret) {
    if(!intersect(a.s, a.e - a.s, Q, w, ret)) return false;
    if(sgn(cross(a.s, a.e, ret)) == 0) return true;
    return false;
}

线段与线段相交同理，代码不再赘述。

点到线的距离

点到线的最短距离其实就是过点做直线的垂线段。我们在旋转向量最后提到了一个法向量，其实就是做这个用的，我们对于这个直线做法向量，然后以这个顶点为起点确定另外一条直线，那么这个点到直线的垂足就算出来了，剩下就是求距离。

求距离也是简单了，我们直接把三点叉乘算出来，底边定为这个直线上的两个点，一除就可以得到高的长度，也就是我们要求的距离了。

1
2
3
4
5
6
7
8
9
10
//点到直线距离
Point disptoline(Point p, Seg l) {
    return fabs(cross(p, l.s, l.e)) / ppdis(l.s, l.e);
}
//点到直线的垂足(最近点)
Point ptoline(Point p, Seg l) {
    Point vec = l.s - l.e;
    // 这里重载了 intersect 函数，使其可以返回点
    return intersect(p, vec.norm(), l.s, vec); 
}

点到线段的最近点会有特殊情况，因为他们的交点有可能不在线段上，那么这时候就需要特判了，但是也没什么大的技术含量，无非多了一个判断左右端点那个更近的说法。

1
2
3
4
5
6
7
8
9
Point ptoseg(Point p, Seg l){
    Point norm = (l.s - l.e).norm();
    if(sgn(norm * (p - l.s)) * sgn(norm * (p - l.e)) > 0) {
            double sa = ppdis(p, l.s);
            double sb = ppdis(p, l.e);
            return sgn(sa - sb) < 0 ? l.s : l.e;
    }
    return intersect(p, norm, l.s, l.e - l.s);
}

至此也算是把大多数直线和线段的简单操作给说了吧，然后我们来看一坨大的。

进阶应用：虔敬的旅人

定义：擘裂冥茫的爪痕

要介绍凸包，首先要介绍一个古老的概念——多边形。多边形有很多很多种，奇形怪状的，自然有凹凸之分。首先明确一个概念，多边形是由至少三边及以上的线段所围成的封闭图形。一定是线段啊，，，小学的时候有一个小孩跑过来和我争论了很久圆是一边形，，，，当时很无语，终于找到铁证了……

那么什么样的多边形被称作凸多边形呢？有一个形式化的说法，就是对于一个凸多边形，你可以任意使一条边变为直线，并且不论你延长的是哪一条边，这条边始终不会让这个多边形分为两部分。这就是凸多边形，也被叫做凸包。你可以随便举几个例子，我们熟知的三角形，矩形什么的全都是凸多边形，而像五角星一类，全都是凹多边形。

由于凸包有很多优良的性质，导致人们很喜欢研究这玩意，接下来就来介绍一些关于凸包的内容，首先我们应该知道如何定义一个凸包类型。

1
2
3
4
5
6
7
// 这个结构体也不只是凸包，也适用于多边形
// 不过有一些函数确实是针对凸包的
struct polygon {
    int n;         // 点的总数（也等于边的总数）
    Point p[maxn]; // 存储点
    Line l[maxn];  // 存储边
}

运算：燎尽黯泽的焰息

接下来我们来处理多边形的构造问题。

建立多边形

首先关于一个多边形的建立，自然离不开点与线。而又由于相邻的两个点可以构成一条线，那么我们不难想到是由点来创造出线。建立起多边形的代码就很简单了：

1
2
3
4
5
6
7
8
void add(point q) {
    p[n++] = q; // 将点 q 加入顶点数组，顶点数递增
}
void getline() {
    for (int i = 0; i < n; i++) {
        l[i] = line(p[i], p[(i + 1) % n]); // 生成边（连接相邻顶点）
    }
}

直接造边的前提是需要按照题目给出点的顺序顺次连接这个点，不然的话如果我们要造凸包，直接来肯定是不行的，所以我们先对点的位置经行规范。

规范预处理

那么既然要构建凸包，我们就需要优先把点按照一个顺序排序，就和贪心一样。有了这个顺序可以更好的辅助我们完成凸包。如何来做？有一个坐标系叫做极坐标系。他是基于一个基准点，然后以角度和距离描述的一个坐标系。这个坐标系就可以使得我们让点以一个顺时针或者逆时针的方式来排序，方便构建凸包。

那么如何判断水的极角大呢？还是那句话，用向量。向量的叉积表示了他们俩为邻边时的平行四边形大小（当然是有向的）我们在三点关系里面讲到了。既然叉积可以判断两个向量谁左谁右亦或者共线，那就轻松判定了极角大小了。

为了方便统一处理，我们就使用类来做极角排序的 compare 函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
struct cmp {
    point p; // 基准点
    cmp(const point &p0) { p = p0; }
    // 让 cmp() 变为比较函数
    bool operator()(const point &a, const point &b) {
        // 计算向量 pa 和 pb 的叉积
        int d = dblcmp(a.sub(p).det(b.sub(p));
        if (d == 0) { // 极角相同，按距离排序
            return dblcmp(a.distance(p) - b.distance(p)) < 0;
        }
        return d > 0; // 叉积为正，a在b的逆时针方向
    }
};

这样算是完成了排序，接下来到了处理凸包的时候了。

凸性质检验

处理凸包，首先要知道如何判断凸包，这样我们就可以了解关于凸包的性质。

那么凸包的话，最明显的性质就是是凸的。我们可以看一下，如果一个多边形的任意一组邻边，它到下一条边所旋转的方向不是同向，那它还是凸的吗？给一个例子：

如何区分凹凸

那么这也是老朋友了，还是叉积即可搞定。

1
2
3
4
5
6
7
8
9
10
bool isconvex() {
    bool s[3] = {0};
    for (int i = 0; i < n; i++) {
        int j = (i + 1) % n, k = (j + 1) % n;
        int d = dblcmp(p[j].sub(p[i]).det(p[k].sub(p[i])));
        s[d + 1] = 1; // 记录转向方向
        if (s[0] && s[2]) return false; // 同时存在左转和右转
    }
    return true;
}

另外提一嘴这里的 dblcmp 函数是判断一个浮点数大于小于或者等于 $0$ 的，这个函数的返回值分别是 $1,-1,0$ 所以说在这个代码中加一存储。

建凸多边形

知道了凸多边形的性质，那么建立一个凸包也就不难了，其实我们已经把点排序了以后，又知道了如何判断凸包，现在要建立一个凸包简直易如反掌。

排序以后的凸包天生按照顺/逆时针给出点以后，我们只需要贪心的维护一个满足凸性质的轮廓即可。因为不可能所有点都能用上（或者说不太可能）阴险的出题人肯定会有干扰选项。但是我们一次就能维护整个凸包吗？看算法。首先来介绍一次只能搞定半个凸包的算法——Andrew算法。

这个算法不是按照我们已经搞过的极角序来排的，而是按照点的横纵坐标来排序，毕竟这个比较符合一般人的常识。那么问题来了，这样就对吗？随便画一个凸包，你就会发现，如果按照横纵坐标排序，单是凸包上的点，就会把上下两部分混在一起。所以我们要分别维护上下凸壳。

代码也不难写，我直接就放上来了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void getconvex(polygon &convex) {
    sort(p, p + n); // 按坐标排序顶点
    // Andrew算法构造上下凸包
    convex.n = n;
    for (int i = 0; i < min(n, 2); i++) convex.p[i] = p[i];
    if (n <= 2) return;
    int &top = convex.n;
    top = 1;
    for (int i = 2; i < n; i++) { // 下凸包
        while (top && convex.p[top].sub(p[i]).det(convex.p[top - 1].sub(p[i])) <= 0)
            top--;
        convex.p[++top] = p[i];
    }
    int temp = top;
    convex.p[++top] = p[n - 2];
    for (int i = n - 3; i >= 0; i--) { // 上凸包
        while (top != temp && convex.p[top].sub(p[i]).det(convex.p[top - 1].sub(p[i])) <= 0)
            top--;
        convex.p[++top] = p[i];
    }
}

然后就是一次能处理整个凸包的 Graham 算法，这个和刚刚的 Andrew 算法完全一样，只变了排序，但是却可以只用一次维护整个凸包，接下来我们直接看代码吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
void getconvex(polygon &convex) {
    // Step 1: 极角排序
    norm();

    // Step 2: 去除重复点
    int m = 0;
    for (int i = 0; i < n; i++) {
        if (i == 0 || !(p[i] == p[i - 1])) {
            p[m++] = p[i];
        }
    }
    n = m;

    convex.n = 0; // 初始化凸包

    if (n == 0) return;

    // 添加前两个点
    convex.add(p[0]);
    if (n == 1) return;

    convex.add(p[1]);
    if (n == 2) return;

    // Step 3: 构建凸包
    for (int i = 2; i < n; i++) {
        // 检查是否需要弹出栈顶元素
        while (convex.n >= 2) {
            point top = convex.p[convex.n - 1];
            point nextTop = convex.p[convex.n - 2];
            int cross = dblcmp((top.sub(nextTop)).det(p[i].sub(nextTop)));
            // 若叉积非正（非左转），弹出
            if (cross <= 0) {
                convex.n--;
            } else {
                break;
            }
        }
        convex.add(p[i]);
    }
}

这样关于凸包的一些信息算是暂时告一段落了。接下来都是一些不论凸凹，多边形都有的性质。

多边形计算

首先来看基本的，周长和面积。周长自不消说，但是如何计算面积呢？一个可行的方法就是把一个多边形分为好几个三角形分别计算面积。但是有人会问这个是否对凹多边形有效，显然是有的，因为如果仔细观察你可以发现，虽然凹多边形会有地方是多算的，但也一定会被算第二次，且这两次计算的结果一定会相互抵消，这是因为叉乘有正有负，自然有抵消的功能。不过最后要把求和后的答案取绝对值，因为我们知道叉乘不满足交换律。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
double getcircumference() {
    double sum = 0;
    for (int i = 0; i < n; i++) {
        sum += p[i].distance(p[(i + 1) % n]); // 累加边长
    }
    return sum;
}
double getarea() {
    double sum = 0;
    for (int i = 0; i < n; i++) {
        sum += p[i].det(p[(i + 1) % n]); // 叉积累加
    }
    return fabs(sum) / 2; // 绝对值除以2
}
bool getdir() {
    double sum = 0;
    for (int i = 0; i < n; i++) {
        sum += p[i].det(p[(i + 1) % n]); // 累加叉积和
    }
    return dblcmp(sum) > 0 ? 1 : 0; // 正为逆时针
}

这里的第三个函数我也不知道有什么用，大概是判断个 $p$ 数组中的顶点是按照什么顺序（顺时针或逆时针）排列的，这个东西我暂且把它放这儿了（

点与多边形

然后是一些常规的几何图形与多边形的关系，这里主要是一些判断点和线与多边形位置关系的函数。首先来看比较简单的点，如何判断一个点是否在多边形内呢？

首先如果一个点在多边形的顶点上或者多边形的边上，这都是非常好判断的，但是如果实在多边形内部呢？这又该如何判断？这里有一个小结论，叫做奇内偶外。简单来说就是以这个点为起点随便做一条射线，如果这条射线经过了多边形的偶数条边，那么他就是在多边形的外面否则是里面。很有趣的结论，可以尝试自己画几个多边形试一试，这是正确的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int relationpoint(point q) {
    for (int i = 0; i < n; i++) if (p[i] == q) return 3; // 顶点
    getline();
    for (int i = 0; i < n; i++) if (l[i].pointonseg(q)) return 2; // 边上
    int cnt = 0; // 射线法计数
    for (int i = 0; i < n; i++) {
        int j = (i + 1) % n;
        int k = dblcmp(q.sub(p[j]).det(p[i].sub(p[j]))); // 叉积判断上下跨立
        int u = dblcmp(p[i].y - q.y), v = dblcmp(p[j].y - q.y);
        if (k > 0 && u < 0 && v >= 0) cnt++;
        if (k < 0 && v < 0 && u >= 0) cnt--;
    }
    return cnt != 0 ? 1 : 0; // 奇内偶外
}

简单的来说，这个其实就是如果这个点不在多边形内，就一定会有一些边一进一出。如果只进不出，只能说明这个多边形其他的边出现在了这个射线的后侧，又因为多边形只能封闭，所以说这个点就在多边形内部了。

线与多边形

这个就是又双叒叕是一个经典问题了。有点与多边形的关系怎么能没有线与多边形的关系呢？那么如何对于线段分类呢？我的代码是将其分为了三类：

  1. 线段在多边形内长度为正
  2. 相交或与边平行
  3. 没有任何交点

然后又是一些模拟，看代码吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int relationline(line u) {
    getline();
    int k = 0;
    for (int i = 0; i < n; i++) {
        // 这个是 Line 类中的一个函数，其返回值含义如下：
        // 2 规范相交
        // 1 非规范相交
        // 0 不相交 
        // 规范相交指的是两个线段的交点在内部而不在端点上。
        int res = l[i].segcrossseg(u);
        if (res == 2) return 1; // 完全相交
        if (res == 1) k = 1;    // 有交点
    }
    if (!k) return 0; // 无交点
    // 检查中点是否在内部
    vector<point> vp;
    for (int i = 0; i < n; i++) {
        if (l[i].segcrossseg(u)) {
            if (l[i].parallel(u)) { // 平行则添加端点
                vp.pb(u.a); vp.pb(u.b); vp.pb(l[i].a); vp.pb(l[i].b);
            } else vp.pb(l[i].crosspoint(u)); // 添加交点
        }
    }
    sort(vp.begin(), vp.end());
    for (int i = 0; i < vp.size() - 1; i++) {
        point mid = vp[i].add(vp[i + 1]).div(2);
        if (relationpoint(mid) == 1) return 1; // 中点在内部
    }
    return 2; // 相交但中点不在内部
}

至此终于完结了多边形的内容，接下来才是真正有难度的知识点。

高阶应用：于死境翩跹

定义：月茧荫蔽的身躯

不卖关子，这个所谓真真有难度的知识点，正是半平面交。什么是半平面呢？我们如果在一个平面上画了一条直线，那么这个平面就被分为了两部分，那么这时候，这个平面的一部分就被称作半平面。如果这条直线被用一次函数的形式描述为了 $ax+by+c$ 那么一般来讲我们题目描述的半平面就是 $ax+by+c\ge 0$ 的一部分。

那么所谓半平面交，就是给出一系列的半平面，求他们的面积交。首先我们来思考一个性质，半平面的交会是个什么多边形呢？一定是凸多边形对吧。因为在这个平面上，一条直线一削就可以让这个多变形的若干边并为一条（前提是有交点）因为我们说过凹多边形的定义是存在有一条边延长可以穿过自己，但是半平面的话相当于直接把超出半平面的部分给舍了，那么只要初始的平面是凸的，半平面交也就一定是凸的。

另外，由于半平面的直线朝向格外重要（即取 $\ge 0$ 的部分或者其他）所以说我们要基于直线类额外建立一个类。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
struct halfplane:public line
{
    double angle;
    halfplane(){}
    //表示向量 a->b逆时针(左侧)的半平面
    halfplane(point _a,point _b)
    {
        a=_a;
        b=_b;
    }
    halfplane(line v)
    {
        a=v.a;
        b=v.b;
    }
    void calcangle() // 计算极角
    {
        angle=atan2(b.y-a.y,b.x-a.x);
    }
    // 保证算法逆时针处理
    bool operator<(const halfplane &b)const 
    {
        return angle<b.angle;
    }
};

然后我们在计算半平面的时候就可以用这个类了。

算法：灼掠幽墟的晦翼

有了这个性质以后，我们就知道了半平面交的本质。那就是用直线切割一个凸多边形。那么其实就是求出这个直线与多边形的交点，然后在这两个交点之间连边，其他的边全部舍去。需要注意的是，如果只有一个交点或者没有交点，这次切割都应该是没有任何效果的。

然后就可以模拟得出结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
// 切割凸包：


struct halfplanes 
{
    int n;
    halfplane hp[maxp];
    point p[maxp];
    int que[maxp];
    int st,ed;
    // 插入半平面
    void push(halfplane tmp)
    {
        hp[n++]=tmp;
    }
    // 对于半平面去重
    void unique()
    {
        int m=1,i;
        for (i=1;i<n;i++)
        {
            // 合并角度相同的部分，如果角度相同判断哪个的左侧区域更小
            if (dblcmp(hp[i].angle-hp[i-1].angle))hp[m++]=hp[i];
            else if (dblcmp(hp[m-1].b.sub(hp[m-1].a).det(hp[i].a.sub(hp[m-1].a))>0))hp[m-1]=hp[i];
        }
        n=m;
    }
    // 计算半平面交
    bool halfplaneinsert()
    {
        int i;
        // 处理极角
        for (i=0;i<n;i++)hp[i].calcangle();
        // 排序后去重
        sort(hp,hp+n);
        unique();
        // 双端队列初始化，优先计算前两个半平面的交点
        // 队列是左开右闭的
        que[st=0]=0;
        que[ed=1]=1;
        p[1]=hp[0].crosspoint(hp[1]);
        for (i=2;i<n;i++)
        {
            // 如果新的半平面使队尾失效
            while (st<ed&&dblcmp((hp[i].b.sub(hp[i].a).det(p[ed].sub(hp[i].a))))<0)ed--;
            // 使队头失效
            while (st<ed&&dblcmp((hp[i].b.sub(hp[i].a).det(p[st+1].sub(hp[i].a))))<0)st++;
            que[++ed]=i; // 插入当前半平面
            // 非法状态，因为已经去过重，仍然出现了平行或者共线的状态
            if (hp[i].parallel(hp[que[ed-1]]))return false;
            // 计算交点
            p[ed]=hp[i].crosspoint(hp[que[ed-1]]);
        }
        // 闭合处理，判断队头或者队尾是否能互相排除
        while (st<ed&&dblcmp(hp[que[st]].b.sub(hp[que[st]].a).det(p[ed].sub(hp[que[st]].a)))<0)ed--;
        while (st<ed&&dblcmp(hp[que[ed]].b.sub(hp[que[ed]].a).det(p[st+1].sub(hp[que[ed]].a)))<0)st++;
        // 判断队列是否为空
        if (st+1>=ed)return false;
        return true;
    }
    // 把最终的交集变为凸包返回
    void getconvex(polygon &con)
    {
        p[st]=hp[que[st]].crosspoint(hp[que[ed]]);
        con.n=ed-st+1;
        int j=st,i=0;
        for (;j<=ed;i++,j++)
        {
            con.p[i]=p[j];
        }
    }
};

至此，算是完成了本文要将的所有内容，我们来吧大模板放上。

模板一览：拥哀歌安眠

这个模板有锅，我再调，所以后面的就先不写了（

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
#include <cassert>
#include <complex>
using namespace std;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define ACCU accumulate
#define TWO(x) (1<<(x))
#define TWOL(x) (1ll<<(x))
#define clr(a) memset(a,0,sizeof(a))
#define POSIN(x,y) (0<=(x)&&(x)<n&&0<=(y)&&(y)<m)
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<double> VD;
typedef long long ll;
typedef long double LD;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef vector<ll> VL;
typedef vector<PII> VPII;
typedef complex<double> CD;
const ll mod=1000000007;
const double eps=1e-9;
const double pi=3.1415926535897932384626;
const int DX[]={1,0,-1,0},DY[]={0,1,0,-1};
ll powmod(ll a,ll b) {ll res=1;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll powmod(ll a,ll b,ll mod) {ll res=1;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
const double inf=1e20;
const int maxp=330;
int dblcmp(double d)
{
    if (fabs(d)<eps)return 0;
    return d>eps?1:-1;
}
inline double sqr(double x){return x*x;}
struct point 
{
    double x,y;
    point(){}
    point(double _x,double _y):
    x(_x),y(_y){};
    void input()
    {
        scanf("%lf%lf",&x,&y);
    }
    void output()
    {
        printf("%.2f %.2f\n",x,y);
    }
    bool operator==(point a)const
    {
        return dblcmp(a.x-x)==0&&dblcmp(a.y-y)==0;
    }
    bool operator<(point a)const
    {
        return dblcmp(a.x-x)==0?dblcmp(y-a.y)<0:x<a.x;
    }
    double len()
    {
        return hypot(x,y);
    }
    double len2()
    {
        return x*x+y*y;
    }
    double distance(point p)
    {
        return hypot(x-p.x,y-p.y);
    }
    point add(point p)
    {
        return point(x+p.x,y+p.y);
    }
    point sub(point p)
    {
        return point(x-p.x,y-p.y);
    }
    point mul(double b)
    {
        return point(x*b,y*b);
    }
    point div(double b)
    {
        return point(x/b,y/b);
    }
    double dot(point p)
    {
        return x*p.x+y*p.y;
    }
    double det(point p)
    {
        return x*p.y-y*p.x;
    }
    double rad(point a,point b)
    {
        point p=*this;
        return fabs(atan2(fabs(a.sub(p).det(b.sub(p))),a.sub(p).dot(b.sub(p))));
    }
    point trunc(double r)
    {
        double l=len();
        if (!dblcmp(l))return *this;
        r/=l;
        return point(x*r,y*r);
    }
    point rotleft()
    {
        return point(-y,x);
    }
    point rotright()
    {
        return point(y,-x);
    }
    point rotate(point p,double angle)//绕点p逆时针旋转angle角度 
    {
        point v=this->sub(p);
        double c=cos(angle),s=sin(angle);
        return point(p.x+v.x*c-v.y*s,p.y+v.x*s+v.y*c);
    }        
};
struct line 
{
    point a,b;
    line(){}
    line(point _a,point _b)
    {
        a=_a;
        b=_b;
    }
    bool operator==(line v)
    {
        return (a==v.a)&&(b==v.b);
    }
    //倾斜角angle 
    line(point p,double angle)
    {
        a=p;
        if (dblcmp(angle-pi/2)==0)
        {
            b=a.add(point(0,1));
        }
        else 
        {
            b=a.add(point(1,tan(angle)));
        }
    }       
    //ax+by+c=0
    line(double _a,double _b,double _c)
    {
        if (dblcmp(_a)==0)
        {
            a=point(0,-_c/_b);
            b=point(1,-_c/_b);
        }
        else if (dblcmp(_b)==0)
        {
            a=point(-_c/_a,0);
            b=point(-_c/_a,1);
        }
        else 
        {
            a=point(0,-_c/_b);
            b=point(1,(-_c-_a)/_b);
        }
    }
    void input()
    {
        a.input();
        b.input();
    }
    void adjust()
    {
        if (b<a)swap(a,b);
    }
    double length()
    {
        return a.distance(b);
    }
    double angle()//直线倾斜角 0<=angle<180 
    {
        double k=atan2(b.y-a.y,b.x-a.x);
        if (dblcmp(k)<0)k+=pi;
        if (dblcmp(k-pi)==0)k-=pi;
        return k;
    }
    //点和线段关系
    //1 在逆时针
    //2 在顺时针
    //3 平行
    int relation(point p)
    {
        int c=dblcmp(p.sub(a).det(b.sub(a)));
        if (c<0)return 1;
        if (c>0)return 2;
        return 3;
    }
    bool pointonseg(point p)
    {
        return dblcmp(p.sub(a).det(b.sub(a)))==0&&dblcmp(p.sub(a).dot(p.sub(b)))<=0;
    }
    bool parallel(line v)
    {
        return dblcmp(b.sub(a).det(v.b.sub(v.a)))==0;
    }
    //2 规范相交
    //1 非规范相交
    //0 不相交 
    int segcrossseg(line v)
    {
        int d1=dblcmp(b.sub(a).det(v.a.sub(a)));
        int d2=dblcmp(b.sub(a).det(v.b.sub(a)));
        int d3=dblcmp(v.b.sub(v.a).det(a.sub(v.a)));
        int d4=dblcmp(v.b.sub(v.a).det(b.sub(v.a)));
        if ((d1^d2)==-2&&(d3^d4)==-2)return 2;
        return (d1==0&&dblcmp(v.a.sub(a).dot(v.a.sub(b)))<=0||
                d2==0&&dblcmp(v.b.sub(a).dot(v.b.sub(b)))<=0||
                d3==0&&dblcmp(a.sub(v.a).dot(a.sub(v.b)))<=0||
                d4==0&&dblcmp(b.sub(v.a).dot(b.sub(v.b)))<=0);        
    }        
    int linecrossseg(line v)//*this seg v line
    {
        int d1=dblcmp(b.sub(a).det(v.a.sub(a)));
        int d2=dblcmp(b.sub(a).det(v.b.sub(a)));
        if ((d1^d2)==-2)return 2;
        return (d1==0||d2==0);
    }
    //0 平行
    //1 重合
    //2 相交 
    int linecrossline(line v)
    {
        if ((*this).parallel(v))
        {
            return v.relation(a)==3;
        }
        return 2;
    }
    point crosspoint(line v)
    {
        double a1=v.b.sub(v.a).det(a.sub(v.a));
        double a2=v.b.sub(v.a).det(b.sub(v.a));
        return point((a.x*a2-b.x*a1)/(a2-a1),(a.y*a2-b.y*a1)/(a2-a1));
    }
    double dispointtoline(point p)
    {
        return fabs(p.sub(a).det(b.sub(a)))/length();
    }
    double dispointtoseg(point p)
    {
        if (dblcmp(p.sub(b).dot(a.sub(b)))<0||dblcmp(p.sub(a).dot(b.sub(a)))<0)
        {
            return min(p.distance(a),p.distance(b));
        }
        return dispointtoline(p);
    }
    point lineprog(point p)
    {
        return a.add(b.sub(a).mul(b.sub(a).dot(p.sub(a))/b.sub(a).len2()));
    }
    point symmetrypoint(point p)
    {
        point q=lineprog(p);
        return point(2*q.x-p.x,2*q.y-p.y);
    }   
};
struct polygon 
{
    int n;
    point p[maxp];
    line l[maxp];
    void input()
    {
        n=4;
        for (int i=0;i<n;i++)
        {
            p[i].input();
        }
    }
    void add(point q)
    {
        p[n++]=q;
    }
    void getline()
    {
        for (int i=0;i<n;i++)
        {
            l[i]=line(p[i],p[(i+1)%n]);
        }
    }
    struct cmp
    {
        point p;
        cmp(const point &p0){p=p0;}
        bool operator()(const point &aa,const point &bb)
        {
            point a=aa,b=bb;
            int d=dblcmp(a.sub(p).det(b.sub(p)));
            if (d==0)
            {
                return dblcmp(a.distance(p)-b.distance(p))<0;
            }
            return d>0;
        }
    };
    void norm()
    {
        point mi=p[0];
        for (int i=1;i<n;i++)mi=min(mi,p[i]);
        sort(p,p+n,cmp(mi));
    }
    void getconvex(polygon &convex)
    {
        int i,j,k;
        sort(p,p+n);
        convex.n=n;
        for (i=0;i<min(n,2);i++)
        {
            convex.p[i]=p[i];
        }
        if (n<=2)return;
        int &top=convex.n;
        top=1;
        for (i=2;i<n;i++)
        {
            while (top&&convex.p[top].sub(p[i]).det(convex.p[top-1].sub(p[i]))<=0)
                top--;
            convex.p[++top]=p[i];
        }
        int temp=top;
        convex.p[++top]=p[n-2];
        for (i=n-3;i>=0;i--)
        {
            while (top!=temp&&convex.p[top].sub(p[i]).det(convex.p[top-1].sub(p[i]))<=0)
                top--;
            convex.p[++top]=p[i];
        }
    }
    bool isconvex()
    {
        bool s[3];
        memset(s,0,sizeof(s));
        int i,j,k;
        for (i=0;i<n;i++)
        {
            j=(i+1)%n;
            k=(j+1)%n;
            s[dblcmp(p[j].sub(p[i]).det(p[k].sub(p[i])))+1]=1;
            if (s[0]&&s[2])return 0;
        }
        return 1;
    }
    //3 点上
    //2 边上
    //1 内部
    //0 外部 
    int relationpoint(point q)
    {
        int i,j;
        for (i=0;i<n;i++)
        {
            if (p[i]==q)return 3;
        }
        getline();
        for (i=0;i<n;i++)
        {
            if (l[i].pointonseg(q))return 2;
        }
        int cnt=0;
        for (i=0;i<n;i++)
        {
            j=(i+1)%n;
            int k=dblcmp(q.sub(p[j]).det(p[i].sub(p[j])));
            int u=dblcmp(p[i].y-q.y);
            int v=dblcmp(p[j].y-q.y);
            if (k>0&&u<0&&v>=0)cnt++;
            if (k<0&&v<0&&u>=0)cnt--;
        }
        return cnt!=0;
    }
    //1 在多边形内长度为正 
    //2 相交或与边平行
    //0 无任何交点 
    int relationline(line u)
    {
        int i,j,k=0;
        getline();
        for (i=0;i<n;i++)
        {
            if (l[i].segcrossseg(u)==2)return 1;
            if (l[i].segcrossseg(u)==1)k=1;
        }
        if (!k)return 0;
        vector<point>vp; 
        for (i=0;i<n;i++)
        {
            if (l[i].segcrossseg(u))
            {
                if (l[i].parallel(u))
                {
                    vp.pb(u.a);
                    vp.pb(u.b);
                    vp.pb(l[i].a);
                    vp.pb(l[i].b);
                    continue;
                }
                vp.pb(l[i].crosspoint(u));
            }
        }
        sort(vp.begin(),vp.end());
        int sz=vp.size();
        for (i=0;i<sz-1;i++)
        {
            point mid=vp[i].add(vp[i+1]).div(2);
            if (relationpoint(mid)==1)return 1;
        }
        return 2;
    }
    //直线u切割凸多边形左侧 
    //注意直线方向 
    void convexcut(line u,polygon &po)
    {
        int i,j,k;
        int &top=po.n;
        top=0;
        for (i=0;i<n;i++)
        {
            int d1=dblcmp(p[i].sub(u.a).det(u.b.sub(u.a)));
            int d2=dblcmp(p[(i+1)%n].sub(u.a).det(u.b.sub(u.a)));
            if (d1>=0)po.p[top++]=p[i];
            if (d1*d2<0)po.p[top++]=u.crosspoint(line(p[i],p[(i+1)%n]));
        }
    }
    double getcircumference()
    {
        double sum=0;
        int i;
        for (i=0;i<n;i++)
        {
            sum+=p[i].distance(p[(i+1)%n]);
        }
        return sum;
    }
    double getarea()
    {
        double sum=0;
        int i;
        for (i=0;i<n;i++)
        {
            sum+=p[i].det(p[(i+1)%n]);
        }
        return fabs(sum)/2;
    }
    bool getdir()//1代表逆时针 0代表顺时针 
    {
        double sum=0;
        int i;
        for (i=0;i<n;i++)
        {
            sum+=p[i].det(p[(i+1)%n]);
        }
        if (dblcmp(sum)>0)return 1;
        return 0;
    }
    point getbarycentre()
    {
        point ret(0,0);
        double area=0;
        int i;
        for (i=1;i<n-1;i++)
        {
            double tmp=p[i].sub(p[0]).det(p[i+1].sub(p[0]));
            if (dblcmp(tmp)==0)continue;
            area+=tmp;
            ret.x+=(p[0].x+p[i].x+p[i+1].x)/3*tmp;
            ret.y+=(p[0].y+p[i].y+p[i+1].y)/3*tmp;
        }
        if (dblcmp(area))ret=ret.div(area);
        return ret;
    }
    double areaintersection(polygon po)
    {
    }
    double areaunion(polygon po)
    {
        return getarea()+po.getarea()-areaintersection(po);
    }     
    int pointinpolygon(point q)//点在凸多边形内部的判定 
    {
        if (getdir())reverse(p,p+n);
        if (dblcmp(q.sub(p[0]).det(p[n-1].sub(p[0])))==0)
        {
            if (line(p[n-1],p[0]).pointonseg(q))return n-1;
            return -1;
        }
        int low=1,high=n-2,mid;
        while (low<=high)
        {
            mid=(low+high)>>1;
            if (dblcmp(q.sub(p[0]).det(p[mid].sub(p[0])))>=0&&dblcmp(q.sub(p[0]).det(p[mid+1].sub(p[0])))<0)
            {
                polygon c;
                c.p[0]=p[mid];
                c.p[1]=p[mid+1];
                c.p[2]=p[0];
                c.n=3;
                if (c.relationpoint(q))return mid;
                return -1;
            }
            if (dblcmp(q.sub(p[0]).det(p[mid].sub(p[0])))>0)
            {
                low=mid+1;
            }
            else 
            {
                high=mid-1;
            }
        }
        return -1;
    }   
};
struct halfplane:public line
{
    double angle;
    halfplane(){}
    //表示向量 a->b逆时针(左侧)的半平面
    halfplane(point _a,point _b)
    {
        a=_a;
        b=_b;
    }
    halfplane(line v)
    {
        a=v.a;
        b=v.b;
    }
    void calcangle()
    {
        angle=atan2(b.y-a.y,b.x-a.x);
    }
    bool operator<(const halfplane &b)const 
    {
        return angle<b.angle;
    }
};
struct halfplanes 
{
    int n;
    halfplane hp[maxp];
    point p[maxp];
    int que[maxp];
    int st,ed;
    void push(halfplane tmp)
    {
        hp[n++]=tmp;
    }
    void unique()
    {
        int m=1,i;
        for (i=1;i<n;i++)
        {
            if (dblcmp(hp[i].angle-hp[i-1].angle))hp[m++]=hp[i];
            else if (dblcmp(hp[m-1].b.sub(hp[m-1].a).det(hp[i].a.sub(hp[m-1].a))>0))hp[m-1]=hp[i];
        }
        n=m;
    }
    bool halfplaneinsert()
    {
        int i;
        for (i=0;i<n;i++)hp[i].calcangle();
        sort(hp,hp+n);
        unique();
        que[st=0]=0;
        que[ed=1]=1;
        p[1]=hp[0].crosspoint(hp[1]);
        for (i=2;i<n;i++)
        {
            while (st<ed&&dblcmp((hp[i].b.sub(hp[i].a).det(p[ed].sub(hp[i].a))))<0)ed--;
            while (st<ed&&dblcmp((hp[i].b.sub(hp[i].a).det(p[st+1].sub(hp[i].a))))<0)st++;
            que[++ed]=i;
            if (hp[i].parallel(hp[que[ed-1]]))return false;
            p[ed]=hp[i].crosspoint(hp[que[ed-1]]);
        }
        while (st<ed&&dblcmp(hp[que[st]].b.sub(hp[que[st]].a).det(p[ed].sub(hp[que[st]].a)))<0)ed--;
        while (st<ed&&dblcmp(hp[que[ed]].b.sub(hp[que[ed]].a).det(p[st+1].sub(hp[que[ed]].a)))<0)st++;
        if (st+1>=ed)return false;
        return true;
    }
    void getconvex(polygon &con)
    {
        p[st]=hp[que[st]].crosspoint(hp[que[ed]]);
        con.n=ed-st+1;
        int j=st,i=0;
        for (;j<=ed;i++,j++)
        {
            con.p[i]=p[j];
        }
    }
}s;

接下来看几道比较经典的例题。

基础例题：素白的新篇

  • 几何例题一

题目大意

解题思路

正确代码

高难例题：以预言装点

  • 几何例题二

题目大意

解题思路

正确代码

算法实战：待奔涌破茧

查看相关算法标签喵！

参考资料（以下排名不分先后）