牛牛机器人 计算几何最核心的问题是浮点数误差
在算法竞赛（如 ACM-ICPC、CCPC、NOI/NOIP）中，计算几何是难度较高但套路相对固定的模块。
以下整理了一份高精度、鲁棒性强且常用的计算几何模板，涵盖了基础结构、向量运算、直线与多边
形处理等核心内容。
一、 基础结构与精度控制
计算几何最核心的问题是浮点数误差。必须使用 eps 进行判零和比较。
cpp
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
// 1. 精度控制
const double EPS = 1e-8;
const double PI = acos(-1.0);
//判断浮点数符号
int sgn(double x) {
if (fabs(x) < EPS) return 0;
return x < 0 ? -1 : 1;
}
// 2. 点结构体
struct Point {
double x, y;
Point() : x(0), y(0) {}
Point(double x, double y) : x(x), y(y) {}
// 向量加法
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); }
// 数乘
Point operator * (double k) const { return Point(x * k, y * k); }
// 数除
Point operator / (double k) const { return Point(x / k, y / k); }
// 叉积 (Cross Product): a x b
// 几何意义：平行四边形面积，判断方向（右手定则）
// >0: b在a逆时针方向; <0: 顺时针; =0: 共线
double operator ^ (const Point& b) const { return x * b.y - y * b.x; }
// 点积 (Dot Product): a . b
// 几何意义：|a||b|cos(theta)，判断夹角锐钝
double operator * (const Point& b) const { return x * b.x + y * b.y; }
// 模长平方
double len2() const { return x * x + y * y; }
// 模长
double len() const { return sqrt(len2()); }
// 极角排序用
bool operator < (const Point& b) const {
if (sgn(x - b.x) != 0) return x < b.x;
return y < b.y;
}
// 判断相等
bool operator == (const Point& b) const {
return sgn(x - b.x) == 0 && sgn(y - b.y) == 0;
}
};
typedef Point Vector;
二、 直线与线段基础操作
cpp
struct Line {
Point s, e; // 起点和终点
Line() {}
Line(Point s, Point e) : s(s), e(e) {}
// 判断点在线段上 (包括端点)
// 前提：点P已经在直线SE上（即叉积为0），只需判断坐标范围
bool point_on_seg(Point p) {
return sgn((p - s) ^ (e - s)) == 0 &&
sgn((p - s) * (p - e)) <= 0;
}
// 两直线交点 (假设不平行)
// 利用面积比求解
Point cross_point(Line l) {
double a1 = (l.e - l.s) ^ (s - l.s);
double a2 = (l.e - l.s)^ (e - l.s);
return Point((s.x * a2 - e.x * a1) / (a2 - a1),
(s.y * a2 - e.y * a1) / (a2 - a1));
}
// 点到直线的距离
double dis_point_to_line(Point p) {
return fabs((p - s) ^ (e - s)) / (e - s).len();
}
// 点到线段的距离
double dis_point_to_seg(Point p) {
if (sgn((p - s) * (e - s)) < 0) return (p - s).len();
if (sgn((p - e) * (s - e)) < 0) return (p - e).len();
return dis_point_to_line(p);
}
};
// 判断两线段是否相交 (快速排斥实验 + 跨立实验)
bool seg_intersects(Line l1, Line l2) {
// 1. 快速排斥：矩形包围盒不相交则线段不相交
if (max(l1.s.x, l1.e.x) < min(l2.s.x, l2.e.x) ||
max(l2.s.x, l2.e.x) < min(l1.s.x, l1.e.x) ||
max(l1.s.y, l1.e.y) < min(l2.s.y, l2.e.y) ||
max(l2.s.y, l2.e.y) < min(l1.s.y, l1.e.y))
return false;
// 2. 跨立实验：互相跨立
double c1 = (l2.s - l1.s)^ (l1.e - l1.s);
double c2 = (l2.e - l1.s) ^ (l1.e - l1.s);
double c3 = (l1.s - l2.s) ^ (l2.e - l2.s);
double c4 = (l1.e - l2.s)^ (l2.e - l2.s);
// 如果允许端点相交，使用 <= 0；如果不允许端点相交（严格内部），使用 < 0
// 这里通常竞赛题允许端点接触算相交，或者根据题目具体要求调整
// 注意处理共线情况：如果 c1==0 && c2==0，需要额外判断投影重叠
if (sgn(c1) == 0 && sgn(c2) == 0) {
// 共线，检查投影是否重叠
return l1.point_on_seg(l2.s) || l1.point_on_seg(l2.e) ||
l2.point_on_seg(l1.s) || l2.point_on_seg(l1.e);
}
return sgn(c1) * sgn(c2) <= 0 && sgn(c3) * sgn(c4) <= 0;
}
三、 多边形核心算法
1. 凸包 (Convex Hull) - Andrew 算法
时间复杂度
𝑂
(
𝑁
log
𝑁
)
O(NlogN)。
cpp
// 求凸包，返回凸包上的点（逆时针顺序）
// 输入点集 pts，输出凸包点集 ch
int convex_hull(vector<Point>& pts, vector<Point>& ch) {
int n = pts.size();
if (n <= 1) {
ch = pts;
return n;
}
sort(pts.begin(), pts.end()); // 按 x 优先，y 次之排序
ch.resize(2 * n);
int k = 0;
// 构建下凸壳
for (int i = 0; i < n; ++i) {
while (k > 1 && sgn((ch[k-1] - ch[k-2]) ^ (pts[i] - ch[k-2])) <= 0)
k--;
ch[k++] = pts[i];
}
// 构建上凸壳
int t = k + 1;
for (int i = n - 2; i >= 0; --i) {
while (k >= t && sgn((ch[k-1] - ch[k-2]) ^ (pts[i] - ch[k-2])) <= 0)
k--;
ch[k++] = pts[i];
}
ch.resize(k - 1); // 最后一个点是起点，重复了，去掉
return ch.size();
}
2. 多边形面积
适用于任意简单多边形（顶点需按顺序给出，顺时针或逆时针均可，结果取绝对值）。
cpp
double polygon_area(const vector<Point>& poly) {
double area = 0;
int n = poly.size();
for (int i = 0; i < n; ++i) {
int j = (i + 1) % n;
area += (poly[i]^ poly[j]);
}
return fabs(area) / 2.0;
}
3. 点在多边形内判断 (射线法)
返回 0: 外部, 1: 内部, -1: 边上。
cpp
int point_in_poly(Point p, const vector<Point>& poly) {
int n = poly.size();
int wn = 0; // winding number
for (int i = 0; i < n; ++i) {
Point p1 = poly[i];
Point p2 = poly[(i + 1) % n];
// 判断是否在边上
if (Line(p1, p2).point_on_seg(p)) return -1;
// 射线法逻辑
if (sgn(p1.y - p.y) <= 0 && sgn(p2.y - p.y) > 0) { // 向上穿过
if (sgn((p2 - p1) ^ (p - p1)) > 0) wn++;
} else if (sgn(p1.y - p.y) > 0 && sgn(p2.y - p.y) <= 0) { // 向下穿过
if (sgn((p2 - p1) ^ (p - p1)) < 0) wn--;
}
}
return wn != 0 ? 1 : 0;
}
四、 旋转卡壳 (Rotating Calipers)
用于求凸多边形直径（最远点对距离平方）。前提是多边形已经是凸包且点按逆时针排列。
cpp
double rotating_calipers_diameter_sq(const vector<Point>& ch) {
int n = ch.size();
if (n == 1) return 0;
if (n == 2) return (ch - ch).len2();
double res = 0;
int q = 1;
for (int p = 0; p < n; ++p) {
// 寻找距离边 (ch[p], ch[p+1]) 最远的点 q
// 当 Area(p, p+1, q+1) > Area(p, p+1, q) 时，q 前进
while (sgn(((ch[(p+1)%n] - ch[p]) ^ (ch[(q+1)%n] - ch[p])) -
((ch[(p+1)%n] - ch[p]) ^ (ch[q] - ch[p]))) > 0) {
q = (q + 1) % n;
}
// 更新最远点对距离 (检查 p-q 和 p+1-q)
res = max(res, (ch[p] - ch[q]).len2());
res = max(res, (ch[(p+1)%n] - ch[q]).len2());
}
return res;
}
五、 使用注意事项与常见坑点
精度陷阱：
永远不要直接用 == 比较 double。
除法前务必判断分母是否为 0（通过 sgn 判断）。
acos 和 asin 的参数可能因误差超出 [-1, 1]，使用前需 min(1.0, max(-1.0, val)) 截断。
共线处理：
在求凸包时，如果题目要求保留共线点，修改 while 条件中的 <= 0 为 < 0。
判断线段相交时，共线情况需要单独处理（投影重叠判断）。
整数 vs 浮点数：
如果输入坐标全是整数，且只涉及加减乘和比较（不涉及开方、三角函数），建议全程使用 long long
进行叉积和点积运算，避免精度误差。只有在最后求距离或角度时才转为 double。
极角排序：
atan2 较慢且有精度问题。推荐使用叉积进行比较排序。若需以某点为中心极角排序，先平移坐标系，再定义比较函数：
cpp
bool cmp_angle(const Point& a, const Point& b) {
double crs = a ^ b;
if (sgn(crs) != 0) return crs > 0;
return a.len2() < b.len2(); // 同向时短的在前
}
这份模板覆盖了竞赛中 80% 以上的计算几何考点。对于更高级的内容（如半平面交、最小圆覆盖、三维几何），建议在掌握上述基础后再单独扩展。
牛牛机器人 / 牛牛算账机器人版权声明：以上内容作者已申请原创保护，未经允许不得转载，侵权必究！授权事宜、对本内容有异议或投诉，敬请联系网站管理员，我们将尽快回复您，谢谢合作！