## 149. Max Points on a Line 原

cofama

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

``````/**
* Definition for a point.
* struct Point {
*     int x;
*     int y;
*     Point() : x(0), y(0) {}
*     Point(int a, int b) : x(a), y(b) {}
* };
*/
class Solution {
public:
int maxPoints(vector<Point>& points) {
int nums = points.size();
int x,y,gcd,duplicate;
pair<int, int> p;
int maxslope, maxline=0;

for(int i=0; i<nums; i++) {
duplicate = 1;
maxslope = 0;
map<pair<int,int>, int> count;
for(int j=i+1; j<nums; j++) {
y = points[j].y-points[i].y;
x = points[j].x-points[i].x;
if(x==0&&y==0) {
duplicate++;
}
else {
gcd = GCD(x,y);
x = x/gcd;
y = y/gcd;
p.first = x;
p.second = y;
count[p]++;
maxslope = max(maxslope, count[p]);
}
}
maxline=max(maxline, maxslope+duplicate);
}
return maxline;
}

private:
int GCD(int a, int b) {
if(b==0) return a;
else return GCD(b, a%b);
}
};
``````

### cofama

leetcode 149. 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. 题意：给一个二维平面，上面有好多点，有横纵坐标，找出一条直线，使得这条线上的点...

2017/10/19
0
0

jimbuster
2007/09/26
0
0
Codeforces I. Barcelonian Distance

07/20
0
0
alibaba.druid.sql.parser.ParserException: unclosed str. pos 92, line 1, column 93, token RPAREN

RonganSchedulerWorker-3] ERROR c.a.d.f.s.StatFilter - [mergeSql,149] - merge sql error, dbType mysql, druid-1.1.14, sql : SELECT MAX(t.`maxtime`) FROM t_rsd_datax_subjob t WHERE......

ios应用猫
09/04
27
0
mysql配置文件不生效以及配置同步复制报错“The server is not configured as slave”解决办法

2014/05/28
0
0

web前端开发高级

44分钟前
6
0
PostgreSQL 11.3 locking

rudi

5
0
Mybatis Plus sql注入器

21
1

5
0

10
0