-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMaxPointOnALine.cc
More file actions
68 lines (59 loc) · 2.22 KB
/
MaxPointOnALine.cc
File metadata and controls
68 lines (59 loc) · 2.22 KB
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
// https://oj.leetcode.com/problems/max-points-on-a-line/
namespace MaxPointOnALine {
/**
* 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) {
if (points.size() <= 2) {
return points.size();
}
int maxPoints = 0;
unordered_map<double, int> map; // <slope, count>
for (int i = 0; i < points.size() - 1; i++) {
map.clear();
int verticalNum = 0;
int samePointNum = 1;
Point p1 = points[i];
for (int j = i + 1; j < points.size(); j++) {
Point p2 = points[j];
if (p1.x == p2.x && p1.y == p2.y) {
samePointNum++;
} else if (p1.x == p2.x) {
verticalNum++;
} else {
double slope = ((double)(p1.y - p2.y)) / (p1.x - p2.x);
unordered_map<double, int>::iterator it = map.find(slope);
if (it == map.end()) {
map[slope] = 1;
} else {
map[slope]++;
}
}
}
// traverse the map to find out the max count with slope
int maxCount = 0;
for (unordered_map<double, int>::iterator it = map.begin(); it != map.end(); it++ ) {
if (it->second > maxCount) {
maxCount = it->second;
}
}
if (verticalNum > maxCount) {
maxCount = verticalNum;
}
maxCount += samePointNum;
if (maxCount > maxPoints) {
maxPoints = maxCount;
}
}
return maxPoints;
}
};
}