2024年蓝桥杯国赛B组蚂蚁开会（洛谷P10907）：线段相交问题的解法

7个月前 (08-27)比赛题解245

一、问题背景

题目模拟了蚂蚁在平面上爬行的轨迹（线段），需要计算所有蚂蚁轨迹线段的整数交点数量。这是典型的计算几何问题，考察线段相交判断和特殊情况的处理能力。

二、完整代码解析（含详细注释）

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);
}

// 计算两条线段的整数交点
bool getIntegerIntersection(const Segment& s1, const Segment& s2, Point& res) {
    Point A = s1.p1, B = s1.p2;
    Point C = s2.p1, D = s2.p2;
    
    long long a1 = B.y - A.y;
    long long b1 = A.x - B.x;
    long long c1 = a1 * A.x + b1 * A.y;
    
    long long a2 = D.y - C.y;
    long long b2 = C.x - D.x;
    long long c2 = a2 * C.x + b2 * C.y;
    
    long long det = a1 * b2 - a2 * b1;
    
    if (det == 0) { // 平行或共线
        // 处理共线情况
        set<Point> points;
        if (onSegment(C, s1)) points.insert(C);
        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;
    
    // 检查是否为整数点
    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) ||
        res.x < min(C.x, D.x) || res.x > max(C.x, D.x) ||
        res.y < min(A.y, B.y) || res.y > max(A.y, B.y) ||
        res.y < min(C.y, D.y) || res.y > max(C.y, D.y)) {
        return false;
    }
    
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<Segment> segments;
    
    for (int i = 0; i < n; ++i) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        segments.emplace_back(Point(x1, y1), Point(x2, y2));
    }
    
    set<Point> intersections;
    
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            Point p;
            if (getIntegerIntersection(segments[i], segments[j], p)) {
                intersections.insert(p);
            }
        }
    }
    
    cout << intersections.size() << endl;
    
    return 0;
}