Số điểm nhiều nhất trên một đường thẳng (Max Points on a Line) trong C++

Cho tập điểm 2D, tìm số điểm lớn nhất thẳng hàng (collinear).

Ví dụ

Điểm: {1,1}, {3,2}, {5,3}, {4,1}, {2,3}, {1,4} → 4 điểm thẳng hàng.

Thuật toán: Duyệt cặp điểm + Đếm

Với mỗi cặp điểm (i-1, i) (sau khi sắp xếp hoặc không), đếm số điểm cùng đường thẳng.

Điều kiện 3 điểm (x1,y1), (x2,y2), (x3,y3) thẳng hàng:

(y3 - y2) * (x2 - x1) == (y2 - y1) * (x3 - x2)

Tránh chia (tránh float, tránh chia cho 0).

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;

class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        int n = points.size();
        if (n < 3) return n;
        int ans = 2;
        for (int i = 1; i < n; i++) {
            int count = 0;
            lli x1 = points[i-1][0], y1 = points[i-1][1];
            lli x2 = points[i][0], y2 = points[i][1];
            if (x1 == x2 && y1 == y2) {
                for (int j = 0; j < n; j++)
                    if (points[j][0] == x1 && points[j][1] == y1) count++;
            } else {
                for (int j = 0; j < n; j++) {
                    int x3 = points[j][0], y3 = points[j][1];
                    if ((y3 - y2) * (x2 - x1) == (y2 - y1) * (x3 - x2)) count++;
                }
            }
            ans = max(ans, count);
        }
        return ans;
    }
};

int main() {
    Solution ob;
    vector<vector<int>> v = {{1,1},{3,2},{5,3},{4,1},{2,3},{1,5}};
    cout << ob.maxPoints(v);
    return 0;
}

Độ phức tạp

• Thời gian: O(n^3) — 3 vòng lặp lồng. Có thể tối ưu thành O(n^2 log n) bằng hash map góc nghiêng cho mỗi điểm gốc.
• Không gian: O(1).

Input / Output

Input:  [{1,1},{3,2},{5,3},{4,1},{2,3},{1,5}]
Output: 4