首页 > 代码库 > Max Points on a Line

Max Points on a Line

2024-07-16 16:44:07   220人阅读

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

思路：对于两个点(x1,y1)和(x2,y2)，其所确定的直线方程为：(x1-x2)*y + (y2-y1)*x + x2*y1-x1*y2 = 0，即：a*y + b*x + c = 0。

        使用类似广度优先遍历的思想，Q[i]保存了第i+1个点与前i个点中的每一个点所确定的直线、以及前i+1个点中经过该直线的点的数目，Q[i][0]表示第i+1个点已经出现的次数。

        依次处理输入序列的每一个元素，对于当前元素i，依次访问每一个Q[k] (k = i-1, i-2, ..., 0)，遍历Q[k]找到经过点i和点k所确定的直线的最大的点的数目，保存在Q[i]中。

        从后往前访问Q[k]的过程中，在第一次遇见点i和点k重合时，更新Q[i][0]的次数值。

 1 class Line 2 { 3  public: 4     Line(): a(0), b(0), c(0), cnt(1) {} 5     ~Line(){} 6  public: 7     int a, b, c; 8     int cnt; 9 };10 11 class Solution {12 public:13     int maxPoints( vector<Point> &points ) {14         if( points.size() <= 2 ) { return points.size(); }15         vector<Line>* Q = new vector<Line>[points.size()];16         Q[0].resize(1);17         int max_num = 2;18         Line optimal;19         for( int i = 1; i < points.size(); ++i ) {20             Q[i].resize(1);21             for( int j = i-1; j >= 0; --j ) {22                 optimal.a = points[i].x-points[j].x;23                 optimal.b = points[j].y-points[i].y;24                 optimal.c = points[j].x*points[i].y-points[i].x*points[j].y;25                 if( points[i].x == points[j].x && points[i].y == points[j].y ) {26                     if( Q[i][0].cnt == 1 ) { Q[i][0].cnt = Q[j][0].cnt+1; }27                     else { continue; }28                     optimal.cnt = Q[i][0].cnt;29                     for( size_t ID = 1; ID != Q[j].size(); ++ID ) {30                         Line& aLine = Q[j][ID];31                         if( aLine.a*points[i].y + aLine.b*points[i].x + aLine.c == 0 ) {32                             if( optimal.cnt <= aLine.cnt+1 ) { optimal = aLine; ++optimal.cnt; }33                         }34                     }35                 } else {36                     optimal.cnt = 2;37                     for( size_t ID = 0; ID != Q[j].size(); ++ID ) {38                         Line& aLine = Q[j][ID];39                         if( aLine.a*points[i].y + aLine.b*points[i].x + aLine.c == 0 ) {40                             if( optimal.cnt < aLine.cnt+1 ) { optimal.cnt = aLine.cnt+1; }41                         }42                     }43                 }44                 if( max_num < optimal.cnt ) { max_num = optimal.cnt; }45                 Q[i].push_back( optimal );46             }47         }48         delete[] Q;49         return max_num;50     }51 };

 

       


联系
我们