• Time:O(n^2)
• Space:O(n)

## C++

``````class Solution {
public:
int maxPoints(vector<vector<int>>& points) {
int ans = 0;

for (int i = 0; i < points.size(); ++i) {
unordered_map<pair<int, int>, int, pairHash> slopeCount;
const vector<int> p1{points[i]};
int samePoints = 1;
int maxPoints = 0;  // maximum number of points with the same slope
for (int j = i + 1; j < points.size(); ++j) {
const vector<int> p2{points[j]};
if (p1 == p2)
++samePoints;
else
maxPoints = max(maxPoints, ++slopeCount[getSlope(p1, p2)]);
}
ans = max(ans, samePoints + maxPoints);
}

return ans;
}

private:
pair<int, int> getSlope(const vector<int>& p, const vector<int>& q) {
const int dx = p[0] - q[0];
const int dy = p[1] - q[1];
if (dx == 0)
return {0, p[0]};
if (dy == 0)
return {p[1], 0};
const int d = __gcd(dx, dy);
return {dx / d, dy / d};
}

struct pairHash {
size_t operator()(const pair<int, int>& p) const {
return p.first ^ p.second;
}
};
};
``````

## JAVA

``````class Solution {
public int maxPoints(int[][] points) {
int ans = 0;

for (int i = 0; i < points.length; ++i) {
Map<Pair<Integer, Integer>, Integer> slopeCount = new HashMap<>();
int[] p1 = points[i];
int samePoints = 1;
int maxPoints = 0; // maximum number of points with the same slope
for (int j = i + 1; j < points.length; ++j) {
int[] p2 = points[j];
if (p1[0] == p2[0] && p1[1] == p2[1])
++samePoints;
else {
Pair<Integer, Integer> slope = getSlope(p1, p2);
slopeCount.merge(slope, 1, Integer::sum);
maxPoints = Math.max(maxPoints, slopeCount.get(slope));
}
}
ans = Math.max(ans, samePoints + maxPoints);
}

return ans;
}

private Pair<Integer, Integer> getSlope(int[] p, int[] q) {
final int dx = p[0] - q[0];
final int dy = p[1] - q[1];
if (dx == 0)
return new Pair<>(0, p[0]);
if (dy == 0)
return new Pair<>(p[1], 0);
final int d = gcd(dx, dy);
return new Pair<>(dx / d, dy / y);
}

private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}
``````

## Python

``````class Solution:
def maxPoints(self, points: List[List[int]]) -> int:
ans = 0

def gcd(a: int, b: int) -> int:
return a if b == 0 else gcd(b, a % b)

def getSlope(p: List[int], q: List[int]) -> Tuple[int, int]:
dx = p[0] - q[0]
dy = p[1] - q[1]
if dx == 0:
return (0, p[0])
if dy == 0:
return (p[1], 0)
d = gcd(dx, dy)
return (dx // d, dy // d)

for i, p in enumerate(points):
slopeCount = defaultdict(int)
samePoints = 1
maxPoints = 0
for j in range(i + 1, len(points)):
q = points[j]
if p == q:
samePoints += 1
else:
slope = getSlope(p, q)
slopeCount[slope] += 1
maxPoints = max(maxPoints, slopeCount[slope])
ans = max(ans, samePoints + maxPoints)

return ans
``````