第十二届蓝桥杯C/C++ B组省赛 第一场 试题C 直线求解

首先定义表示一个顶点的结构体

struct Point {
    int x, y;

    Point(int x, int y) : x(x), y(y) {
    }

    //向量减法
    Point operator-(Point &point) const {
        return {x - point.x, y - point.y};
    }
};

根据两点确定一条直线，我们可以写一个表示直线的类，使用直线的一般式Ax+By+C=0，表示任意的一条直线，其中数据成员有A,B,C三个系数，为了数据精度以及便于判断相等，尽量避免使用浮点数运算。

那么，已知两个整数坐标表示的点我们可通过两点式按如下数学推导，计算出直线方程。

所以此时有，

需要注意的是，两点式使用的前提为直线的斜率不能不存在或不能为0，所以当发生上述限制时需要单独计算直线方程。

Point delta = p2 - p1;
if (delta.x == 0) {   //如果直线斜率不存在
    //那么最后的直线方程为 x = a.x
    A = 1;
    B = 0;
    C = -p1.x;
} else if (delta.y == 0) {
    //最后直线方程为y = a.y
    A = 0;
    B = 1;
    C = -p1.y;
} else {
    A = delta.y;
    B = -delta.x;
    C = delta.x * p1.y - delta.y * p1.x;
}

为了便于直线的去重，下一步我们需要对直线的三个系数A,B,C进行适当的约分使得其最简。

为了约分，首先我们编写计算最大公约数的函数如下，

//求两整数的最大公约数
int gcd(int x, int y) {
    int r = x % y;
    while (r != 0) {
        x = y;
        y = r;
        r = x % y;
    }
    return y;
}

//多整数的最大公约数计算
int gcd(std::vector<int> nums) {
    int num = nums[0];
    for (int i = 1; i < nums.size(); i++) {
        num = gcd(num, nums[i]);
    }
    return num;
}

编写对A,B,C的约分函数如下，

//系数约分化
void reduce() {
    std::vector<int> ks;
    if (A != 0)
        ks.push_back(A);
    if (B != 0)
        ks.push_back(B);
    if (C != 0)
        ks.push_back(C);
    int gcd_num = gcd(ks);  //求最大公约数

    A /= gcd_num;
    B /= gcd_num;
    C /= gcd_num;
}

此时，判断约分后的A,B,C是否相等即可判断是否为同一直线。

//根据题目条件，获取指定范围内的所有整数顶点
std::vector<Point> getAllPoints(int startX, int endX, int startY, int endY) {
    std::vector<Point> result;
    for (int x = startX; x < endX; x++) {
        for (int y = startY; y < endY; y++) {
            result.emplace_back(x, y);
        }
    }
    return result;
}

对所有直线两两组合，并且检查重复性，即可完成最后的直线集的求解

//获取所有未去重的直线
std::vector<Line> getLines(std::vector<Point> points) {
    std::vector<Line> result;
    for (int i = 0; i < points.size() - 1; i++) {
        for (int j = i + 1; j < points.size(); j++) {
            Line line(points[i], points[j]);
            auto it = find(result.begin(), result.end(), line);
            if (it == result.end()) { //找不到
                result.push_back(line);
            }
        }
    }
    return result;
}

完整代码如下

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Point {
    int x, y;

    Point(int x, int y) : x(x), y(y) {
    }

    //向量减法
    Point operator-(Point &point) const {
        return {x - point.x, y - point.y};
    }
};

//求两整数的最大公约数
int gcd(int x, int y) {
    int r = x % y;
    while (r != 0) {
        x = y;
        y = r;
        r = x % y;
    }
    return y;
}

//多整数的最大公约数计算
int gcd(std::vector<int> nums) {
    int num = nums[0];
    for (int i = 1; i < nums.size(); i++) {
        num = gcd(num, nums[i]);
    }
    return num;
}

struct Line {
    int A, B, C;   //直线Ax+By+C = 0

    //构造直线
    Line(Point &p1, Point &p2) {
        Point delta = p2 - p1;
        if (delta.x == 0) {   //如果直线斜率不存在
            //那么最后的直线方程为 x = a.x
            A = 1;
            B = 0;
            C = -p1.x;
        } else if (delta.y == 0) {
            //最后直线方程为y = a.y
            A = 0;
            B = 1;
            C = -p1.y;
        } else {
            A = delta.y;
            B = -delta.x;
            C = delta.x * p1.y - delta.y * p1.x;
        }

        reduce();
    }

    //系数约分化
    void reduce() {
        std::vector<int> ks;
        if (A != 0)
            ks.push_back(A);
        if (B != 0)
            ks.push_back(B);
        if (C != 0)
            ks.push_back(C);
        int gcd_num = gcd(ks);  //求最大公约数

        A /= gcd_num;
        B /= gcd_num;
        C /= gcd_num;
    }


    //判断两直线是否为同一直线
    bool operator==(Line line) const {
        return (A == line.A) && (B == line.B) && (C == line.C);
    }
};

//获取所有顶点
std::vector<Point> getAllPoints(int startX, int endX, int startY, int endY) {
    std::vector<Point> result;
    for (int x = startX; x < endX; x++) {
        for (int y = startY; y < endY; y++) {
            result.emplace_back(x, y);
        }
    }
    return result;
}

//获取所有去重的直线
std::vector<Line> getLines(std::vector<Point> points) {
    std::vector<Line> result;
    for (int i = 0; i < points.size() - 1; i++) {
        for (int j = i + 1; j < points.size(); j++) {
            Line line(points[i], points[j]);
            auto it = find(result.begin(), result.end(), line);
            if (it == result.end()) { //找不到
                result.push_back(line);
            }
        }
    }
    return result;
}


int main() {
    auto points = getAllPoints(0, 20, 0, 21);
    vector<Line> lines = getLines(points);
    cout << lines.size() << endl;

    return 0;
}

最后答案求得40257