C++ | Leetcode C++题解之第149题直线上最多的点数
题目：
题解：
class Solution {
public:int gcd(int a, int b) {return b ? gcd(b, a % b) : a;}int maxPoints(vector<vector<int>>& points) {int n = points.size();if (n <= 2) {return n;}int ret = 0;for (int i = 0; i < n; i++) {if (ret >= n - i || ret > n / 2) {break;}unordered_map<int, int> mp;for (int j = i + 1; j < n; j++) {int x = points[i][0] - points[j][0];int y = points[i][1] - points[j][1];if (x == 0) {y = 1;} else if (y == 0) {x = 1;} else {if (y < 0) {x = -x;y = -y;}int gcdXY = gcd(abs(x), abs(y));x /= gcdXY, y /= gcdXY;}mp[y + x * 20001]++;}int maxn = 0;for (auto& [_, num] : mp) {maxn = max(maxn, num + 1);}ret = max(ret, maxn);}return ret;}
};