-
Notifications
You must be signed in to change notification settings - Fork 0
/
149 Max Points on a Line.cpp
44 lines (41 loc) · 1.17 KB
/
149 Max Points on a Line.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution
{
public:
int maxPoints(vector<Point> &points)
{
if(points.size()<2) return points.size();
int result=0;
for(int i=0; i<points.size(); i++)
{
map<pair<int, int>, int> lines;
int localmax=0, overlap=0, vertical=0;
for(int j=i+1; j<points.size(); j++)
{
if(points[j].x==points[i].x && points[j].y==points[i].y)
{
overlap++;
continue;
}
else if(points[j].x==points[i].x) vertical++;
else
{
int a=points[j].x-points[i].x, b=points[j].y-points[i].y;
int gcd=GCD(a, b);
a/=gcd;
b/=gcd;
lines[make_pair(a, b)]++;
localmax=max(lines[make_pair(a, b)], localmax);
}
localmax=max(vertical, localmax);
}
result=max(result, localmax+overlap+1);
}
return result;
}
private:
int GCD(int a, int b)
{
if(b==0) return a;
else return GCD(b, a%b);
}
};