Hướng dẫn giải

Một ngôi sao \((x, y)\) nhìn thấy từ gốc nếu không có ngôi sao nào khác nằm trên cùng tia \((kx, ky)\) với \(0 < k < 1\).

Hai điểm nằm trên cùng tia với 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 \((dx / g, dy / g)\) với \(g = \gcd(|dx|, |dy|)\) làm định danh cho mỗi tia. Số lượng tia khác nhau chính là số ngôi sao nhìn thấy.

Có thể dùng \(\text{set}\) hoặc sắp xếp để đếm các cặp \((dx/g, dy/g)\) riêng biệt.

Độ phức tạp: \(O(n \log n)\).

Mã nguồn C++

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

int main() {
    int n;
    cin >> n;
    set<pair<int, int>> dirs;
    for (int i = 0; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        int g = __gcd(abs(x), abs(y));
        dirs.insert({x / g, y / g});
    }
    cout << dirs.size() << "\n";
    return 0;
}