题目:
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
解题思路:
1,在所有点中选定一个点作为中心点,然后再求剩下的点到该中心点的斜率,如果斜率相同的点表示在同一直线上
2,如果剩下点中有与中心点相同的点,则记下相同点的个数,然后直接跳过,继续下一个点到中心点斜率的求解
3,为了防止重复计算,当以节点i作为中心节点时,剩余的点表示为数组中i点后面的点
实现代码:
#include <iostream>
#include <vector>
#include <map>
#include <limits>
#include <unordered_map>
using namespace std; /* */
struct Point {
int x;
int y;
Point() : x(), y() {}
Point(int a, int b) : x(a), y(b) {}
}; class Solution {
public:
int maxPoints(vector<Point> &points) {
if(points.size() == )
return ;
int max = ;
map<double, int> umap;
for(int i = ; i < points.size(); i++)
{
int tmp_max = ;//当已第i个点位中心时,同一直线上点数最大值
umap.clear();
int repeat = ;//与i点相同点的个数
for(int j = i+; j < points.size(); j++)
{
double slope = numeric_limits<double>::infinity();
if(points[j].x != points[i].x)
slope = double(points[j].y - points[i].y) / (points[j].x - points[i].x);
else if(points[j].y == points[i].y)//与中心点相同的点
{
repeat++;
continue;
}
umap[slope]++;//到中心点斜率相同的点数++,这里umap中存在该斜率,则直接将该斜率对应的值++,否则先添加,再++
if(umap[slope] > tmp_max)
tmp_max = umap[slope];
}
tmp_max += repeat;//以i为中心点出发的每一条直线上的点数都应该加上repeat,因为与i点相同的点在所有从i出发的直线上
if(tmp_max > max)
max = tmp_max;//更新全局最大值 }
return max + ; //之前所求的每一条直线上的点数都没有加上该直线的中心点,所以这里要加上1
}
}; int main(void)
{
Point ps[] = {{,},{,},{,}};
int len = sizeof(ps) / sizeof(Point);
vector<Point> points(ps, ps+len);
Solution solution;
int ret = solution.maxPoints(points);
cout<<ret<<endl;
return ;
}