首先定义表示一个顶点的结构体
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
