观前提醒：「文章仅供学习和参考，如有问题请在评论区提出」
只是整理了一些基本的二维计算模板，参考资料都在最后。
每个模板都试了试具体的可行性，基本上应该没有什么错误（大概）。如果有问题，请及时联系我进行修改。
基本设置
long double
// 输入输出
scanf("%Lf", &x);
printf("%.6Lf\n", x);
// 函数使用: fabsl(), cosl()
常数定义
const double eps = 1e-8; // 根据题目精度要求进行修改
const double PI = acos(-1.0); // pai, 3.1415916....
int sgn(double x) { // 进行判断, 提高精度
if (fabs(x) < eps) return 0; // x == 0, 精度范围内的近似相等
return x > 0 ? 1 : -1; // 返回正负
}
点 + 向量
Point（Vector）
向量：点 \(A(x_{1}, y_{1}), B(x_{2}, y_{2})\) ，那么向量 \(\vec{AB} = B - A = (x_{2} - x_{1}, y_{2} - y_{1})\) 。
Point(x, y) 代表点 \(A=(x, y)\) , Vector(x, y) 代表向量 \(\vec{B} = (x, y)\) 。
// Need: sgn()
typedef struct Point {
double x, y;
Point(double x = 0, double y = 0) : x(x), y(y) {} // 构造函数, 初始值为 0
// 重载操作符
// 点 - 点 = 向量(向量AB = B - A)
Point operator- (const Point &B) const { return Point(x - B.x, y - B.y); }
// 点 + 点 = 点, 点 + 向量 = 向量, 向量 + 向量 = 向量
Point operator+ (const Point &B) const { return Point(x + B.x, y + B.y); }
// 向量 × 向量 (叉积)
double operator^ (const Point &B) const { return x * B.y - y * B.x; }
// 向量 · 向量 (点积)
double operator* (const Point &B) const { return x * B.x + y * B.y; }
// 点 * 数 = 点, 向量 * 数 = 向量
Point operator* (const double &B) const { return Point(x * B, y * B); }
// 点 / 数 = 点, 向量 / 数 = 向量
Point operator/ (const double &B) const { return Point(x / B, y / B); }
// 判断大小, 一般用于排序
bool operator< (const Point &B) { return x < B.x || (x == B.x && y < B.y); }
// 判断相等, 点 == 点, 向量 == 向量, 一般用于判断和去重
bool operator== (const Point &B){ return sgn(x - B.x) == 0 && sgn(y - B.y) == 0; }
// 判断不相等, 点 != 点, 向量 != 向量
bool operator!= (const Point &B) { return sgn(x - B.x) || sgn(y - B.y); }
} Vector;
点积（数量积、内积）（Dot）
向量 \(\vec{a}(x_{1}, y_{1}), \vec{b}(x_{2}, y_{2})\) ，\(\vec{a} \cdot \vec{b} = | \vec{a} | | \vec{b} | \cos \theta = x_{1}x_{2} + y_{1}y_{2}\) 。
\(\theta\) 表示向量 \(\vec{a}\) 旋转到向量 \(\vec{b}\) 所经过的夹角。
// 向量 · 向量 (点积)
double operator* (Vector &A, Vector &B) { return A.x * B.x + A.y * B.y; }
夹角 \(\theta\) 与点积大小的关系：
- 若 \(\theta = 0^{o}\) ，\(\vec{a} \cdot \vec{b} = |\vec{a}||\vec{b}|\) 。
- 若 \(\theta = 180^{o}\) ，\(\vec{a} \cdot \vec{b} = -|\vec{a}||\vec{b}|\) 。
- 若 \(\theta < 90^{o}\) ，\(\vec{a} \cdot \vec{b} > 0\) 。
- 若 \(\theta = 90^{o}\) ，\(\vec{a} \cdot \vec{b} = 0\) 。
- 若 \(\theta > 90^{o}\) ，\(\vec{a} \cdot \vec{b} < 0\) 。
向量积，叉积（Cross）
向量 \(\vec{a}(x_{1}, y_{1}), \vec{b}(x_{2}, y_{2})\) ，\(\vec{a} \times \vec{b} = | \vec{a} | | \vec{b} | \sin \theta = x_{1}y_{2} - x_{2}y_{1}\) 。
\(\theta\) 表示向量 \(\vec{a}\) 旋转到向量 \(\vec{b}\) 所经过的夹角。
// 向量 × 向量 (叉积)
double operator^ (Vector &A, Vector &B) { return A.x * B.y - A.y * B.x; }
两点间距离（Dist）
点 \(a(x_{1}, y_{1}), b(x_{1}, y_{1})\) ，\(ab = \sqrt{(x_{1} - x_{2})^{2} + (y_{1} - y_{2})^{2}}\)
// Need: (-, *)
double dist(Point a, Point b) { return sqrt((a - b) * (a - b)); }
向量的模（Len）
向量 \(\vec{a}(x, y)\) ，\(|\vec{a}| = \sqrt{x^{2} + y^{2}}\) 。
// Need: (*)
double len(Vector A) { return sqrt(A * A); }
单位向量（Norm）
// Need: (/), len()
Vector norm(Vector A) { return A / len(A); }
两向量的夹角（Angle）
由 \(\vec{a} \cdot \vec{b} = | \vec{a} | | \vec{b} | \cos \theta\) ，得 $cos \theta = \frac{\vec{a} \cdot \vec{b}}{| \vec{a} | | \vec{b} |} $ ，即 $\theta = \arccos \frac{\vec{a} \cdot \vec{b}}{| \vec{a} | | \vec{b} |} $ 。
// Need: (*), len(), PI
double Angle(Vector A, Vector B) {
double t = acos((A * B) / len(A) / len(B));
return t; // 返回 [0, π]
return t * (180 / PI); // 返回 [0, 180] (角度)
}
判断点在直线（向量）的哪边（Cross）
// Need: (-, ^), sgn()
// 点在直线上, 返回 0 (三点共线)
// 点在直线的逆时针方向, 返回 1
// 点在直线的顺时针方向, 返回 -1
// 点 a, b (向量ab) 所在的直线和点 c
// 使用的时候要注意 a 和 b 的顺序, 有时顺序不同, 结果不同
int Cross(Point a, Point b, Point c) { return sgn((b - a) ^ (c - a)); }
逆转角（Rotate）
将向量 \(A\) 逆时针旋转 \([0, \pi]\) 。
// Need: (*, ^)
// 向量 A 和要逆时针转的角度 [0, PI]
// PI / 2, 90度
Vector Rotate(Vector A, double b) {
Vector B(sin(b), cos(b));
return Vector(A ^ B, A * B);
}
线
直线表达式
- 一般式：\(ax + by + c = 0\)
- 点向式：直线上一点 \((x_{0}, y_{0})\) 和方向向量 \((u, v)\) ，有 \(\frac{x - x_{0}}{u} = \frac{y - y_{0}}{v}, (u \ne 0, v \ne 0)\)
- 斜截式：\(y = kx + b\)
Line
struct Line {
Point s, e;
Line() {}
Line(Point x, Point y):s(x), e(y) {}
};
判断三点共线（In_one_line）
如果三点 \(A(x_{1}, y_{1}), B(x_{2}, y_{2}), C(x_{3}, y_{3})\) 共线，等价为 \(\vec{AB} \times \vec{BC} = 0\) 。
// Need: sgn(), 操作符重载(-, ^)
bool In_one_line(Point A, Point B, Point C) { return !sgn((B - A) ^ (C - B)); }
点到直线的距离（Dist_point_to_line)
\(\vec{a} \times \vec{b} = | \vec{a} | | \vec{b} | \sin \theta = | \vec{a} | d\) ，那么 \(d = \frac{\vec{a} \times \vec{b}}{| \vec{a} |}\) 。
// Need: (-, ^), len()
// 点 P 到直线 AB 的距离
double Dist_point_to_line(Point P, Point A, Point B) {
Vector v1 = B - A, v2 = P - A;
return fabs((v1 ^ v2) / len(v1));
}
点到线段的距离（Dist_point_to_seg）
// Need: 操作符重载(==, -, *, ^), len(), sgn()
double Dist_point_to_seg(Point P, Point A, Point B) {
if (A == B) return len(P - A); // 如果重合, 那么就是两点的距离
Vector v1 = B - A, v2 = P - A, v3 = P - B;
if (sgn(v1 * v2) < 0) return len(v2); // AP 最短
if (sgn(v1 * v3) > 0) return len(v3); // BP 最短
return fabs((v1 ^ v2) / len(v1)); // 垂线
}
判断点是否在线段上（OnSegment）
// Need: (-, *, ^), sgn()
bool OnSegment(Point P, Point A, Point B) {
Vector PA = A - P, PB = B - P;
return sgn(PA ^ PB) == 0 && sgn(PA * PB) <= 0; // <=, 包括端点; <, 不包括端点
}
判断直线与线段是否相交（Intersect_line_seg）
// Need: Cross()
// 相交, 返回 true
// 不相交, 返回 false
// 直线 ab 与线段 cd
bool Intersect_line_seg(Point a, Point b, Point c, Point d) {
return Cross(a, b, c) * Cross(a, b, d) <= 0;
}
判断两线段是否相交（Intersect_seg）
// Need: Cross()
// 相交, 返回 true (包括端点相交)
// 不相交, 返回 false
// 线段 ab 与线段 cd
bool Intersect_seg(Point a, Point b, Point c, Point d) {
if (Cross(a, b, c) * Cross(a, b, d) > 0) return 0;
if (Cross(c, d, a) * Cross(c, d, b) > 0) return 0;
return 1;
}
判断两直线平行（Line_parallel)
// Need: (-, ^), sgn()
bool Line_relation(Line A, Line B) { // 返回true: 平行/重合, false: 相交
return sgn((A.s - A.e) ^ (B.s - B.e)) == 0;
}
求两直线交点（Intersection_line)
直线的两点式 \((a, c)\) 转化为点向式 \((a, c - a)\) 。
// Need: (-, *D, ^)
// 首先要判断两直线是否相交, 即不平行(不重合)
// a, b 所在直线与 c, d 所在直线的交点
Point Intersection_line(Point a, Point b, Point c, Point d) {
Vector u = b - a, v = d - c;
double t = ((a - c) ^ v) / (v ^ u);
return a + u * t;
}
// Need: (-, *D, ^)
Point Intersection_line(Point a, Vector, Point b, Vector v) {
double t = ((a - b) ^ v) / (v ^ u);
return a + u * t;
}
多边形
三角形面积（Triangle_area）
海伦公式 ：\(S = \sqrt{p(p - a)(p - b)(p - c)}, p = \frac{a + b + c}{2}\)
// Need: 操作符重载(-), len()
double Triangle_area(Point A, Point B, Point C) {
double a = len(A - B), b = len(A - C), c = len(B - C);
double p = (a + b + c) / 2;
return sqrt(p * (p - a) * (p - b) * (p - c));
}
已知三角形两边及夹角，$S = \frac{1}{2}ab\sin C = \frac{1}{2}bc\sin A = \frac{1}{2}ac\sin B $
过原点的三角形面积为 \(S_{ \triangle OAB} = \frac{1}{2} |\vec{OA} \times \vec{OB}|\)
那么把三角形一点移到原点（假设是 \(A\) ），那么就有 \(S_{\triangle ABC} = \frac{1}{2} |\vec{AB} \times \vec{AC}|\) 。
// Need: (-, ^)
double Triangle_area2(Point A, Point B, Point C) {
return fabs((B - A) ^ (C - A)) / 2;
}
三角形四心
-
外心：三边中垂线的交点，到三角形三个顶点的距离相同（外接圆圆心）。
-
内心：角平分线的交点，到三角形三边的距离相同（内切圆圆心）。
-
垂心：三条垂线的交点。
-
重心：三条中线的交点，到三角形三顶点距离的平方和最小的点，三角形内到三边距离之积最大的点。
三角形重心是三点各坐标的平均值 \((\frac{x_{1} + x_{2} + x_{3}}{3}, \frac{y_{1} + y_{2} + y_{3}}{3})\) 。
正弦定理 & 余弦定理
正弦定理
在三角形 \(\triangle ABC\) 中，若角 \(A, B, C\) 所对应的边为 \(a, b, c\) ，则有
\[\frac{a}{\sin A} = \frac{b}{\sin B} = \frac{c}{\sin C} = 2R
\]
其中，\(R\) 为 \(\triangle ABC\) 的外接圆半径。
余弦定理
在三角形 \(\triangle ABC\) 中，若角 \(A, B, C\) 所对应的边为 \(a, b, c\) ，则有
\[\begin{align}
a^{2} = b^{2} + c^{2} - 2bc \cos A \\
b^{2} = a^{2} + c^{2} - 2ac \cos A \\
c^{2} = a^{2} + b^{2} - 2ab \cos A \\
\end{align}
\]
正多边形的一些性质和概念
内角
正 \(n\) 边形的内角和度数为：\((n - 2)\times 180^{0}\)
正 \(n\) 边形的一个内角为：\(\frac{(n - 2)\times180^{0}}{n}\)
外角
正 \(n\) 边形外角和度数为：\(n \times 180^{0} - (n - 2) \times 180^{0} = 360^{0}\)
正 \(n\) 边形的一个外角为：\(\frac{360^{0}}{n}\)
所以正 \(n\) 边形的一个内角也可以是：\(180^{0} - \frac{360^{0}}{n}\)
中心角
多边形的重心就是它所作外接圆的圆心，所以中心角度数为：\(\frac{360°}{n}\)
正 \(n\) 边形对角线数量为：\(\frac{n(n - 3)}{2}\)
求多边形面积（Polygon_area)
// Need: (-, ^)
// 因为叉积求得的三角形面积是有向的, 在外面的面积可以正负抵消掉
// 所以能够求任意多边形面积(凸, !凸)
// p[]下标从 0 开始, 长度为 n
double Polygon_area(Point *p, int n) {
double area = 0;
for (int i = 1; i <= n - 2; i++)
area += (p[i] - p[0]) ^ (p[i + 1] - p[0]);
return fabs(area / 2); // 无向面积
return area / 2; // 有向面积
}
鞋带定理（Shoelace formula）
\[\begin{align} &A_{1}(x_{1}, y_{1}), A_{2}(x_{2}, y_{2}), A_{3}(x_{3}, y_{3}),...,A_{n}(x_{n}, y_{n}) \\ &S = \frac{1}{2} \left | {\textstyle \sum_{i = 1}^{n}} (x_{i}y_{i + 1} - x_{i + 1}y_{i}) \right | \\ \end{align} \]
// Need: (^)
// 原理和上面相同, 不过是把原点(0, 0) 作为被指向点
// p[] 下标从 0 开始, 长度为 n
double Polygon_area(Point *p, int n) {
double area = 0;
for (int i = 0, j = n - 1; i < n; j = i++)
area += (p[j] ^ p[i]);
return fabs(area / 2); // 无向面积
return area / 2; // 有向面积
}
判断点在多边形内（InPolygon）
射线法
以被测点 \(P\) 为端点，向任意方向作射线（一般水平向右作射线），统计该射线与多边形的交点数（不包括多边形顶点）。
如果为奇数，点 \(P\) 在多边形内；如果为偶数，点 \(P\) 在多边形外。
如果点 \(P\) 的纵坐标比多边形某边的纵坐标都大（都小），那么他们的交点一定在延长线上。
因为是以 \(P(x_{0}, y_{0})\) 为端点，水平向右作射线，要想判断有没有交点，所以只需要判断同 \(y_{0}\) 坐标下，\(x_{0}\) 是否在 \(x\) 的左边。
\[\begin{align} &k = \frac{y_{1} - y_{2}}{x_{1} - x_{2}} \\ 代入(x_{1}, y_{1}), 得 \enspace &b = y_{1} - \frac{y_{1} - y_{2}}{x_{1} - x_{2}}x_{1} \\ \enspace &y = \frac{y_{1} - y_{2}}{x_{1} - x_{2}}x - \frac{y_{1} - y_{2}}{x_{1} - x_{2}}x_{1} + y_{1} \\ 代入 y_{0}, 得 \enspace &x = (y_{0} - y_{1}) \frac{x_{1} - x_{2}}{y_{1} - y_{2}} + x_{1} \end{align} \]
// Need: sgn(), OnSegment()
// 适用于任意多边形, 不用考虑精度误差和多边形的给出顺序
// 点在多边形边上, 返回 -1
// 点在多边形内, 返回 1
// 点在多边形外, 返回 0
// p[] 的下标从 0 开始, 长度为 n
int InPolygon(Point P, Point *p, int n) {
bool flag = false; // 相当于计数
for (int i = 0, j = n - 1; i < n; j = i++) {
Point p1 = p[i], p2 = p[j];
if (OnSegment(P, p1, p2)) return -1;
if (sgn(P.y - p1.y) > 0 == sgn(P.y - p2.y) > 0) continue;
if (sgn((P.y - p1.y) * (p1.x - p2.x) / (p1.y - p2.y) + p1.x - P.x) > 0)
flag = !flag;
}
return flag;
}
判断凸多边形（Is_convex）
// Need: (-, ^), sgn()
// 顶点必须按顺时针(或逆时针)给出, 允许共线边
// p[] 下标从 0 开始, 长度为 n
bool Is_contex(Point *p, int n) {
bool s[3];
memset(s, 0, sizeof (s));
for (int i = 0, j = n - 1, k = n - 2; i < n; k = j, j = i++) {
int cnt = sgn((p[i] - p[j]) ^ (p[k] - p[j])) + 1;
s[cnt] = true;
if (s[0] && s[2]) return false;
}
return true;
}
圆
Circle
弧长公式：\(L = \alpha \times r\) ，弧长 = 半径 × 圆心角。
// Need: Point()
struct Circle {
Point o;
double r;
Circle(Point _o = Point(), double _r = 0) : o(_o), r(_r) {}
// 圆的面积
double Circle_S() { return PI * r * r; }
// 圆的周长
double circle_C() { return 2 * PI * r; }
};
扇形的面积（SectorArea）
设扇形的半径为 \(r\) ，弧长为 \(l\) ，面积为 \(S\) ，圆心角为 \(\alpha\) ，那么有
\[S = \frac{1}{2}lr = \frac{1}{2} \alpha r^2 \]
// Need: (^), Angle(), sgn()
// 扇形的两交点A, B 和圆的半径 R
double SectorArea(Point A, Point B, double R) {
double angle = Angle(A, B);
if (sgn(A ^ B) < 0) angle = -angle;
return R * R * angle / 2;
}
点与圆的位置关系（Point_with_circle）
// Need: sgn(), dist()
// 点在圆上, 返回 0
// 点在圆外, 返回 -1
// 点在圆内, 返回 1
int Point_with_circle(Point p, Circle c) {
double d = dist(p, c.o);
if (sgn(d - c.r) == 0) return 0;
if (sgn(d - c.r) > 0) return -1;
return 1;
}
直线与圆的位置关系（Line_with_circle）
// Need: sgn(), Dist_point_to_line()
// 相切, 返回 0
// 相交, 返回 1
// 相离, 返回 -1
int Line_with_circle(Point A, Point B, Circle c) {
double d = Dist_point_to_line(c.o, A, B);
if (sgn(d - c.r) == 0) return 0;
if (sgn(d - c.r) > 0) return -1;
return 1;
}
求直线与圆的交点（Intersection_line_circle）
// Need: (-, +, *P, *D, /), sgn()
// 直线与圆相交, 返回两点
// 直线与圆相切, 返回两个一样的相切点
pair<Point, Point> Intersection_line_circle(Point A, Point B, Circle c) {
Vector AB = B - A;
Vector pr = A + AB * ((c.o - A) * AB / (AB * AB));
double base = sqrt(c.r * c.r - ((pr - c.o) * (pr - c.o)));
if (sgn(base) == 0) return make_pair(pr, pr);
Vector e = AB / sqrt(AB * AB);
return make_pair(pr + e * base, pr - e * base);
}
圆与圆的位置关系（Circle_with_circle）
// Need: dist()
// 相离, 返回 -1
// 外切, 返回 0
// 内切(A 包含 B), 返回 1
// 内切(B 包含 A), 返回 2
// 内含(A 包含 B), 返回 3
// 内含(B 包含 A), 返回 4
// 相交, 返回 5
int Circle_with_circle(Circle A, Circle B) {
double len1 = dist(A.o, B.o);
double len2 = A.r + B.r;
if (sgn(len1 - len2) > 0) return -1;
if (sgn(len1 - len2) == 0) return 0;
if (sgn(len1 + len2 - 2 * A.r) == 0) return 1;
if (sgn(len1 + len2 - 2 * B.r) == 0) return 2;
if (sgn(len1 + len2 - 2 * A.r) < 0) return 3;
if (sgn(len1 + len2 - 2 * B.r) < 0) return 4;
return 5;
}
圆与圆的交点（Intersection_circle_circle）
// Need: (-, +), len()
// 相交, 返回两点坐标
// 相切, 返回两个一样的相切点
// 要先判断是否相交或相切再调用
pair<Point, Point> Intersection_circle_circle(Circle A, Circle B) {
Vector AB = B.o - A.o;
double d = len(AB);
double a = acos((A.r * A.r + d * d - B.r * B.r) / (2.0 * A.r * d));
double t = atan2(AB.y, AB.x);
Vector x(A.r * cos(t + a), A.r * sin(t + a));
Vector y(A.r * cos(t - a), A.r * sin(t - a));
return make_pair(A.o + x, A.o + y);
}
求圆外一点对圆的两个切点（TangentPoint_point_circle）
// Need: (-, *, ^, +), dist()
// 返回两个切点坐标
// 一定要先判断点在圆外, 然后再调用
pair<Point, Point> TangentPoint_point_circle(Point p, Circle c) {
double d = dist(p, c.o);
double l = sqrt(d * d - c.r * c.r);
Vector e = (c.o - p) / d;
double angle = asin(c.r / d);
Vector t1(sin(angle), cos(angle));
Vector t2(sin(-angle), cos(-angle));
Vector e1(e ^ t1, e * t1);
Vector e2(e ^ t2, e * t2);
e1 = e1 * l + p;
e2 = e2 * l + p;
return make_pair(e1, e2);
}
求三角形的外接圆（get_circumcircle）
已知 \(\triangle ABC\) 的三个顶点 \(A(x_1, y_1), B(x_2, y_2), C(x_3, y_3)\)，假设其外接圆圆心为 \(O(x_0, y_0)\) ，半径为 \(r\) 。
根据外接圆圆心的特点，圆心到三点的距离相等，有
\[(x_1 - x_0)^2 + (y_1 - y_0)^2 = (x_2 - x_0)^2 + (y_2 - y_0)^2 = (x_3 - x_0)^2 + (y_3 - y_0)^2 \]推导出，
\[\begin{align} &x_0 = \frac{(y_2 - y_1)(y_3^2 - y_1^2 + x_3^2 - x_1^2) - (y_3 - y_1)(y_{2}^{2} - y_1^2 + x_2^2 - x_1^2)}{2(x_3 - x_1)(y_2 - y_1) - 2(x_2 - x_1)(y_3 - y_1)} \\ &y_0 = \frac{(x_2 - x_1)(x_3^2 - x_1^2 + y_3^2 - y_1^2) - (x_3 - x_1)(x_{2}^{2} - x_1^2 + y_2^2 - y_1^2)}{2(y_3 - y_1)(x_2 - x_1) - 2(y_2 - y_1)(x_3 - x_1)} \\ &r = \sqrt{(x_1 - x_0)^2 + (y_1 - y_0)^2} \end{align} \]
// Need: dist()
Circle get_circumcircle(Point A, Point B, Point C) {
double Bx = B.x - A.x, By = B.y - A.y;
double Cx = C.x - A.x, Cy = C.y - A.y;
double D = 2 * (Bx * Cy - By * Cx);
double x = (Cy * (Bx * Bx + By * By) - By * (Cx * Cx + Cy * Cy)) / D + A.x;
double y = (Bx * (Cx * Cx + Cy * Cy) - Cx * (Bx * Bx + By * By)) / D + A.y;
Point P(x, y);
return Circle(P, dist(A, P));
}
求三角形的内切圆（get_incircle）
// Need: (*D, /), dist(), Dist_point_to_line()
Circle get_incircle(Point A, Point B, Point C) {
double a = dist(B, C);
double b = dist(A, C);
double c = dist(A, B);
Point p = (A * a + B * b + C * c) / (a + b + c);
return Circle(p, Dist_point_to_line(p, A, B));
}
网格
求线段上整点个数（IntegerPoint_on_seg)
// 要保证传入的点是整点
int IntegerPoint_on_seg(Point A, Point B) {
int x = abs(A.x - B.x);
int y = abs(A.y - B.y);
if (x == 0 || y == 0) return 1;
return __gcd(x, y) + 1; // 包含端点
return __gcd(x, y) - 1; // 不包含端点
}
求多边形上整点个数（IntegerPoint_on_polygon）
// 返回多边形边上整点的个数
// 点需要是顺时针(逆时针)给出
// p[] 下标从 0 开始, 长度为 n
int IntegerPoint_on_polygon(Point *p, int n) {
int res = 0;
for (int i = 0, j = n - 1; i < n; j = i++) {
int x = abs(p[i].x - p[j].x);
int y = abs(p[i].y - p[j].y);
res += __gcd(x, y);
}
return res;
}
多边形内整点个数（IntegerPoint_in_polygon）
皮克定理（Pick‘s Theorem）
任一顶点在网格上的封闭多边形，面积为 \(A\) ，内部格点数为 \(I\) ，边界上格点数为 \(B\) 。那么有
\[A = I + \frac{1}{2}B - 1 \]
// Need: Polygon_area(), IntegerPoint_on_polygon()
// 返回不包括边界的, 多边形内整点个数
int IntegerPoint_in_polygon(Point *p, int n) {
double A = Polygon_area(p, n);
double B = IntegerPoint_on_polygon(p, n);
return A - B / 2 + 1;
}
极角排序
// Need: (-, ^), len(), sgn()
// 排序常数大, 但精度高
Point p[N]; // 要排序的点
Point o(0, 0); // 极点自定义
// 获取象限 (0, 1, 2, 3)
int Quadrant(Vector p) { return sgn(p.y < 0) << 1 | sgn(p.x < 0) ^ sgn(p.y < 0); }
// 比较函数
bool cmp(Point a, Point b) {
Vector p = a - o, q = b - o;
int x = Quadrant(p), y = Quadrant(q);
if (x == y) {
if (sgn(p ^ q) == 0) return len(p) < len(q);
return sgn(p ^ q) > 0;
}
return x < y;
}
凸包 Andrew算法
给定平面上的点集，凸包就是将最外层的点连接起来构成的凸多边形，它能包含点集中的所有点。
Andrew算法：\(O(nlogn)\)
// Need: (<), Cross(), dist()
Point s[N]; // 用来存凸包多边形的顶点
int top = 0;
// 点集 p[] 的下标从 1 开始, 长度为 n
double Andrew(Point *p, int n) {
sort(p + 1, p + n + 1);
for (int i = 1; i <= n; i++) { // 下凸包
while (top > 1 && Cross(s[top - 1], s[top], p[i]) <= 0) top--;
s[++top] = p[i];
}
int t = top;
for (int i = n - 1; i >= 1; i--) { // 上凸包
while (top > t && Cross(s[top - 1], s[top], p[i]) <= 0) top--;
s[++top] = p[i];
}
top--; // 因为首尾都会加一次第一个点, 所以去掉最后一个
double res = 0;
for (int i = 1; i < top; i++) res += dist(s[i], s[i + 1]);
return res; // 凸多边形周长
}
最小圆覆盖问题
在一个平面上有 \(n\) 个点，求一个半径最小的圆，能覆盖所有的点。
随机增量法：\(O(n)\)
// Need: (+, /), sgn(), dist(), get_circumcircle()
// p[] 下标从 0 开始, 长度为 n
Circle get_min_circle(Point *p, int n) {
// 随机化, 防止被卡
for (int i = 0; i < n; i++) swap(p[rand() % n], p[rand() % n]);
Point o = p[0];
double r = 0;
for (int i = 0; i < n; i++) {
if (sgn(dist(o, p[i]) - r) <= 0) continue;
o = (p[i] + p[0]) / 2;
r = dist(p[i], p[0]) / 2;
for (int j = 1; j < i; j++) {
if (sgn(dist(o, p[j]) - r) <= 0) continue;
o = (p[i] + p[j]) / 2;
r = dist(p[i], p[j]) / 2;
for (int k = 0; k < j; k++) {
if (sgn(dist(o, p[k]) - r) <= 0) continue;
o = get_circumcircle(p[i], p[j], p[k]).o;
r = dist(o, p[i]);
}
}
}
return Circle(o, r);
}
圆与多边形的面积交
给定一个多边形和圆，求多边形和圆的面积交。
思路：三角剖分
// Need: (-, +, *D, *, ^, /), sgn(), Intersection_line(点向量版), OnSegment(), Rotate()
// SectorArea(), Angle(), norm(), len(), dist(),
// 返回圆点到 ab 线段的距离, 并带回圆与线段的交点 pa, pb
double getDP2(Point a, Point b, Circle c, Point &pa, Point &pb) {
Point o = c.o;
double R = c.r;
Point e = Intersection_line(a, b - a, o, Rotate(b - a, PI / 2)); // 垂足点
double d = dist(o, e);
if (!OnSegment(e, a, b)) d = min(dist(o, a), dist(o, b));
if (R <= d) return d;
double Len = sqrt(R * R - dist(o, e) * dist(o, e));
pa = e + norm(a - b) * Len;
pb = e + norm(b - a) * Len;
return d;
}
double getArea(Point a, Point b, Circle C) { // 面积的交
Point o = C.o;
double R = C.r;
if (sgn(a ^ b) == 0) return 0; // 共线
double da = dist(o, a), db = dist(o, b);
if (sgn(R - da) >= 0 && sgn(R - db) >= 0) return (a ^ b) / 2; // ab 在圆内
Point pa, pb;
double d = getDP2(a, b, C, pa, pb);
if (sgn(R - d) <= 0) return SectorArea(a, b, R); // ab 在圆外
if (sgn(R - da) >= 0) return (a ^ pb) / 2 + SectorArea(pb, b, R); // a 在圆内
if (sgn(R - db) >= 0) return SectorArea(a, pa, R) + (pa ^ b) / 2; // b 在圆内
return SectorArea(a, pa, R) + (pa ^ pb) / 2 + SectorArea(pb, b, R); // ab 是割线
}
// 返回所求的面积交
double Intersection_Area(Point *p, int n, Circle C) {
// 平移
for (int i = 0; i < n; i++) p[i] = p[i] - C.o;
C.o = Point(0.0, 0.0);
double area = 0;
for (int i = 0, j = n - 1; i < n; j = i++) area += getArea(p[j], p[i], C);
return fabs(area);
}
参考资料
计算几何的模板（大神整理）_计算几何模板_clasky的博客-CSDN博客
详谈判断点在多边形内的七种方法（最全面）WilliamSun0122的博客-CSDN博客