思想为：统计每个点的各个斜率的直线上有多少个点
C++代码：
#include <iostream> #include <vector> #include <map> #include <cstdlib> #include <ctime> // 随机数通用公式:a + rand() % n；其中的a是起始值，n是整数的范围 /* 要取得[a,b)的随机整数，使用(rand() % (b-a))+ a; 要取得[a,b]的随机整数，使用(rand() % (b-a+1))+ a; 要取得(a,b]的随机整数，使用(rand() % (b-a))+ a + 1; 要取得0～1之间的浮点数，可以使用rand() / double(RAND_MAX) */ #define RANDOM(a, b) ( (rand() % ((b)-(a) + 1)) + (a) ) // 计算 [a, b] 之间的随机整数 using namespace std; struct Point2D { Point2D(int X, int Y) : x(X),y(Y) {} int x; int y; }; int maxPoints(const vector<Point2D>& pointVec) {// 计算二维平面上，共线最多的点数。 if(pointVec.size() <= 2) return pointVec.size(); unsigned int Max = 0; for(vector<Point2D>::size_type i=0; i < pointVec.size(); i++) { map<double, unsigned int> m;// <斜率， 点数> unsigned int duplicate = 0/*和点 i 重复的点数量*/, infiniteSlope = 1/*过点 i 斜率无穷大的点数量*/, _max = 0/*记录当过点 i 的直线上最多的点数*/; for(vector<Point2D>::size_type j=i+1; j < pointVec.size(); j++) { if(pointVec[i].x == pointVec[j].x) { if(pointVec[i].y == pointVec[j].y)// 重复的点 ++duplicate; else ++infiniteSlope; } else { double slope = (pointVec[i].y-pointVec[j].y)*1.0f / (pointVec[i].x-pointVec[j].x);// 点 i 和点 j 的斜率 m[slope] == 0 ? (m[slope] = 2) : ++m[slope]; _max = max(_max, m[slope]); } } _max = max(_max, infiniteSlope) + duplicate; Max = max(Max, _max); } return Max; } vector<Point2D> getPoint2DVec(const unsigned int M, const unsigned int N, unsigned int k=0) {// 若 k 等于 0，在 M×N 平面上随机产生 1~M×N 个随机点 vector<Point2D> pointVec; if(M > 0 && N > 0) { srand((unsigned)time(NULL));// 生成随机数种子 if(0 == k) { k = RANDOM(1, (M+1)*(N+1));// 在平面随机产生 k 个点 cout << "随机产生了 " << k << " 个点" << endl; } for(unsigned int i=0; i < k; i++) { int x = RANDOM(0, M); int y = RANDOM(0, N); pointVec.push_back(Point2D(x, y)); cout << x << ", " << y << endl; } } return pointVec; } int main() { int M, N;// 平面大小 while(cin >> M >> N) { cout << "平面大小：" << M << " × " << N << endl; if(M > 0 && N > 0) { vector<Point2D> pointVec = getPoint2DVec(M, N); cout << "最多有 " << maxPoints(pointVec) << " 个点共线" << endl; } } return 0; }