2024蓝桥杯国赛B组蚂蚁开会题解析：线段整数交点算法实现（C++代码详解）
2个月前 (08-22)
一、题目解读
2024年蓝桥杯国赛B组“蚂蚁开会”题目要求解决平面上多条线段交点数量的统计问题。题目中，蚂蚁在二维平面上的线段上移动，需要计算所有线段交点的数量，且交点必须为整数坐标。该问题本质是几何算法中的线段交点判断，需考虑共线、整数坐标等特殊条件，对算法的严谨性和边界处理有较高要求。
二、解题思路
核心思路是通过计算线段交点并验证整数坐标来实现。关键在于：
1. 数据结构定义：使用 Point（存储坐标）和 Segment（存储线段）结构体，重载 < 运算符便于排序。
2. 叉积计算：通过 cross() 函数判断三点关系（左/右侧或共线），避免浮点数误差。
3. 交点判断：
若两线段平行或共线，通过 onSegment() 检查端点重合，返回首个重合点。
若相交，计算交点坐标并验证是否为整数（通过叉积分母判断余数）。
4. 去重与统计：利用集合存储交点，自动去重。
三、解题步骤
1. 输入处理：读取线段端点坐标，构建 Segment 对象集合。
2. 循环遍历：双重循环枚举所有线段组合。
3. 调用 getIntegerIntersection()：
计算叉积判断位置关系。
共线时，提取重合端点存入集合。
相交时，通过代数方法计算交点坐标，验证整数性后存入。
4. 输出结果：集合大小即为交点数量。
四、代码与注释
// 点结构体重载比较运算符（用于后续排序）
struct Point {
int x, y;
Point(int x=0, int y=0) : x(x), y(y) {}
bool operator<(const Point& other) const {
return x < other.x || (x == other.x && y < other.y); // 按坐标字典序排序
}
};
// 线段结构体
struct Segment {
Point p1, p2;
Segment(Point p1, Point p2) : p1(p1), p2(p2) {}
};
// 叉积计算：判断三点相对位置（左/右/共线）
long long cross(const Point& a, const Point& b, const Point& c) {
return (long long)(b.x - a.x) * (c.y - a.y) - (long long)(b.y - a.y) * (c.x - a.x);
}
// 判断点是否在线段上（含端点）
bool onSegment(const Point& p, const Segment& s) {
if (cross(s.p1, s.p2, p)!= 0) return false; // 不共线则不在
return p.x >= min(s.p1.x, s.p2.x) && p.x <= max(s.p1.x, s.p2.x) && // 横坐标范围
p.y >= min(s.p1.y, s.p2.y) && p.y <= max(s.p1.y, s.p2.y); // 纵坐标范围
}
// 计算两线段的整数交点（存在则返回true，存入res）
bool getIntegerIntersection(const Segment& s1, const Segment& s2, Point& res) {
Point A = s1.p1, B = s1.p2; // 线段1端点
Point C = s2.p1, D = s2.p2; // 线段2端点
// 计算两线段的代数方程系数（ax + by + c = 0）
long long a1 = B.y - A.y, b1 = A.x - B.x, c1 = a1 * A.x + b1 * A.y; // 线段1方程
long long a2 = D.y - C.y, b2 = C.x - D.x, c2 = a2 * C.x + b2 * C.y; // 线段2方程
long long det = a1 * b2 - a2 * b1; // 系数矩阵行列式（判断平行）
if (det == 0) { // 平行或共线
// 处理共线情况：提取重合的端点
set<Point> points;
if (onSegment(C, s1)) points.insert(C); // 检查C是否在s1上
if (onSegment(D, s1)) points.insert(D);
if (onSegment(A, s2)) points.insert(A);
if (onSegment(B, s2)) points.insert(B);
if (points.size() > 0) {
res = *points.begin(); // 返回第一个重合点
return true;
}
return false; // 无重合点则无交点
}
// 计算交点坐标（代数方法）
long long x = b2 * c1 - b1 * c2;
long long y = a1 * c2 - a2 * c1;
// 验证是否为整数（叉积分母 det 整除分子）
if (x % det!= 0 || y % det!= 0) return false; // 非整数则跳过
res.x = x / det; // 赋值整数交点
res.y = y / det;
// 检查交点是否在线段上（边界条件）
if (res.x < min(A.x, B.x) || res.x > max(A.x, B.x) || // 超出s1范围
res.y < min(A.y, B.y) || res.y > max(A.y, B.y) ||
res.x < min(C.x, D.x) || res.x > max(C.x, D.x) || // 超出s2范围
res.y < min(C.y, D.y) || res.y > max(C.y, D.y)) {
return false; // 交点在线段外则无效
}
return true; // 合法整数交点
}
// 主函数调用示例（省略，用户可根据题目输入格式自行实现）五、总结
本解法通过叉积与代数方程结合，高效处理线段交点问题，核心优化在于：
1. 整数性判断：利用行列式整除特性避免浮点数误差。
2. 共线处理：通过集合存储重合端点，简化逻辑且自动去重。
3. 边界严谨性：交点需同时满足在线段上及整数坐标，确保答案正确。
适用于蓝桥杯竞赛中涉及几何计算与精度要求的场景，为同类问题提供通用算法模板。
原创内容 转载请注明出处
