forked from fanfank/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
max-points-on-a-line.cpp
42 lines (42 loc) · 1.31 KB
/
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
/**
* 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) {
map<double, int> m;
int res = 0;
for(int i = 0; i < points.size(); ++i) {
m.clear();
int tmpmax = 0, vertical = 0, overlap = 1;
for(int j = i + 1; j < points.size(); ++j) {
int dy = points[i].y - points[j].y, dx = points[i].x - points[j].x;
double k = 0;
if(dx == 0) {
if(dy == 0)
++overlap;
else
tmpmax = max(tmpmax, ++vertical);
} else {
if(dy == 0) {
tmpmax = max(tmpmax, ++(m[0]));
} else {
int minus = (dy * dx < 0)?-1 : 1;
dy = dy < 0? -dy : dy;
dx = dx < 0? -dx : dx;
k = (dy * 1.0 / dx) * minus;
tmpmax = max(tmpmax, ++(m[k]));
}
}
}
res = max(res, tmpmax + overlap);
}
return res;
}
};