首页 > 代码库 > Max Points on a Line 149
Max Points on a Line 149
题目描述：
给出平面内的n个点，求最多有多少各点在同一条直线上
题目分析：
同一条直线上的点，任意两个点之间对应相同的斜率
这样我们固定一个点s（我们称为起始点），求出其他所有点与起始点构成向量的斜率
那么这些斜率中相同的，他们对应的点与起始点在同一条直线上
为了，能快速找到重复次数最多的斜率，我们对斜率排序，这样可以在总时间nlogn时间内找出重复次数最多的点
然后，替换起始点重复上面操作，总的时间复杂度是n*nlogn
注意：
在计算斜率时，对于斜率无穷大的要拿出来特殊考虑（所有斜率无穷大的点，与起始点都在同一条直线上）
对于与起始点重合的点也要特殊考虑，这种点是一定与起始点在同一条直线上的
比较斜率时候相等时，不要用‘==’ ，double类型比较相等时可以两个数相减，结果如果小于一个很小的数，认为两个数相等
代码：
1 bool equal(double x,double y){ 2 if(fabs(x-y)<10e-6)return true; 3 return false; 4 } 5 6 int maxPoints(vector<Point> &points){ 7 int len=points.size(); 8 if(len<=2)return len; 9 10 double slope[len];/// 存储斜率11 int ma=0;12 for(int i=0;i<len-1;i++){13 int vertical =1;///与i点垂直方向上的点数，因为这个时候dx==0不能计算斜率，要单独计算14 int samePoint=1;///与i点在同一位置上的点的个数15 int cnt=0;16 for(int j=i+1;j<len;j++){17 int dx=points[i].x-points[j].x;18 int dy=points[i].y-points[j].y;19 if(dx==0){20 if(dy==0) samePoint++;21 else vertical++;22 }23 else slope[cnt++]=(double)dy/dx;24 }25 26 ma=max(ma,vertical+samePoint-1);///减1，因为在vertical和samePoint中都包含i点27 if(cnt==0)return ma;28 29 sort(slope,slope+cnt);30 int repCnt=1+samePoint;31 for(int j=1;j<cnt;j++){32 if(equal(slope[j],slope[j-1]))repCnt++;33 else {34 ma=max(ma,repCnt);35 repCnt=1+samePoint;36 }37 }38 if(repCnt>ma)ma=repCnt;39 }40 return ma;41 }
Max Points on a Line 149
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。