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

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

1
2
3
4
5
6
7
8
9
10
11
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三个系数，为了数据精度以及便于判断相等，尽量避免使用浮点数运算。

那么，已知两个整数坐标表示的点P1(x1,y1),P2(x2,y2)P_1(x_1,y_1),P_2(x_2,y_2)我们可通过两点式按如下数学推导，计算出直线方程。

根据两点式

\begin{equation} \begin{split} \frac{x-x_1}{x_2-x_1} &= \frac{y-y_1}{y_2-y_1} \\ (x-x_1)(y_2-y_1) &= (y-y_1)(x_2-x_1)\\ (y_2-y_1)x-(y_2-y_1)x_1 &= (x_2-x_1)y-(x_2-x_1)y_1\\ \end{split} \end{equation}\\ 即: (y_2-y_1)x - (x_2-x_1)y+(x_2-x_1)y_1-(y_2-y_1)x_1 = 0

所以此时有，

\begin{equation} \begin{split} A &= y_2-y_1\\ B &= -(x_2-x_1)\\ C &= (x_2-x_1)y_1-(y_2-y_1)x_1 \end{split} \end{equation}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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进行适当的约分使得其最简。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//求两整数的最大公约数
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的约分函数如下，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//系数约分化
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是否相等即可判断是否为同一直线。

1
2
3
4
5
6
7
8
9
10
//根据题目条件，获取指定范围内的所有整数顶点
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;
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//获取所有未去重的直线
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;
}

完整代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#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