Hướng dẫn giải

Hai điểm nằm trên cùng đường thẳng qua gốc khi và chỉ khi vector chỉ phương của chúng tỉ lệ với nhau. Sử dụng phân số tối giản \((x / g, y / g)\) với \(g = \gcd(|x|, |y|)\) làm khoá, đếm tần suất xuất hiện của mỗi khoá.

Kết quả là tần suất lớn nhất trong các khoá.

Chú ý: cần xử lý dấu sao cho các cặp \((x, y)\) và \((-x, -y)\) được xem là cùng đường thẳng. Có thể chuẩn hoá bằng cách đưa \(x\) về dương (hoặc nếu \(x = 0\) thì đưa \(y\) về dương).

Độ phức tạp: \(O(n \log M)\) với \(M = \max(|x|, |y|)\).

Mã nguồn C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    map<pair<int, int>, int> cnt;
    for (int i = 0; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        int g = __gcd(abs(x), abs(y));
        x /= g; y /= g;
        if (x < 0 || (x == 0 && y < 0)) {
            x = -x;
            y = -y;
        }
        cnt[{x, y}]++;
    }
    int ans = 0;
    for (auto &p : cnt) ans = max(ans, p.second);
    cout << ans << "\n";
    return 0;
}