最多共线点的数目

Love The Way You Lie 2022-08-26 04:49 137阅读 0赞

本题目来自LeetCode，具体内容如下：

### Max Points on a Line ###

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

题目叙述很简单，就是给定2D平面上的N个点，从这些点中找出共线的点的集合，输出元素最多的那个集合。

对于这个题目，有两种思路：

1. 对于任意的两个点A 和 B，然后遍历剩下的所有点，检测是否与A 、B两点共线，并统计共线的点的个数。在这过程中记录最大的共线点的个数，最后得到的就是要求的解。

因此这是一个三重循环，时间复杂度是O(N^3)

2.对于每一个点A，计算其与剩下所有点的连线的斜率。然后对斜率进行排序，从中找出出现次数最多的，作为经过点A的共线的点的最大个数。

对于每一个点都做同样的操作，最后就可以得到为题的解。 其时间复杂度是O(N^2logN)，如果把对斜率的排序算法换成hash，就可以进一步提高时间效率，达到O(N^2).

注意：上面两种方法都需要特别注意对重复点的处理。

下面给出第一种思路的AC代码（所有测试代码），如有错误之处，请大家批评指正：

#include <iostream>
    #include <string>
    #include <algorithm>
    #include <stack>
    #include <vector>
    #include <fstream>
    using namespace std;
    
    struct Point {
    	int x;
    	int y;
    	Point() : x(0), y(0) {}
    	Point(int a, int b) : x(a), y(b) {}
    };
    
    class Solution {
    public:
    	bool isCollineation(Point& p1, Point& p2, Point& p3) //判断三点是否共线
    	{
    		int x1 = p1.x - p2.x ;
    		int y1 = p1.y - p2.y ;
    		int x2 = p1.x - p3.x ;
    		int y2 = p1.y - p3.y ;
    		if (x1 * y2 - x2 * y1 == 0)
    			return true ;
    		return false ;
    	} ;
        int maxPoints(vector<Point> &points) {
    
            if (points.size() <= 2) return points.size() ;
    		int maxLine = 2 ;
    
    		bool flag = false ; //用来表示是否所有的点都重合
    		for (size_t i = 0; i < points.size(); ++ i)
    		{
    			int cpyNum = 0 ; //重复出现的点的个数
    			for (size_t j = i + 1; j < points.size(); ++ j)
    			{
    				if (points[i].x == points[j].x && points[i].y == points[j].y)
    				{
    					cpyNum ++ ;
    					continue ;
    				}
    				flag = true ;
    				int count = 2 + cpyNum ;
    				for (size_t k = j + 1; k < points.size(); ++ k)
    					if (isCollineation(points[i], points[j], points[k]))
    						count ++ ;
    				if (count > maxLine)
    					maxLine = count ;
    			}
    		}
    
    		if (!flag) maxLine = points.size() ;
    		return maxLine ;
        }
    };
    
    int main(int argc, char** argv)
    {
    
    	ifstream in("data.txt") ;
    	int x = 0, y = 0 ;
    	vector<Point> points ;
    	while (in >> x >> y)
    		points.push_back(Point(x, y)) ;
    
    	Solution s ;
    	cout << s.maxPoints(points) << endl;
    	return 0 ;
    }

测试文件的内容：

0 9  
138 429  
115 359  
115 359  
\-30 -102  
230 709  
\-150 -686  
\-135 -613  
\-60 -248  
\-161 -481  
207 639  
23 79  
\-230 -691  
\-115 -341  
92 289  
60 336  
\-105 -467  
135 701  
\-90 -394  
\-184 -551  
150 774  
115 359  
115 359

输出结果是：14