Hướng dẫn giải của Đếm bộ ba thẳng hàng
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Tác giả:
Subtask 1 — ~N ≤ 500~ (30%)
Duyệt tất cả bộ ba ~i < j < k~. Ba điểm ~P_i~, ~P_j~, ~P_k~ thẳng hàng khi:
~(x_j - x_i)(y_k - y_i) = (y_j - y_i)(x_k - x_i)~.
Nếu điều kiện trên đúng thì tăng đáp án.
Độ phức tạp: ~O(N^3)~.
Subtask 2 — ~N ≤ 2000~ (70%)
Cố định mỗi điểm ~P_i~. Với mọi điểm ~P_j ≠ P_i~, tính vector ~(dx, dy)~, sau đó chuẩn hóa bằng gcd và chuẩn hóa dấu để các vector cùng phương có cùng biểu diễn.
Sắp xếp các vector. Với mỗi nhóm có ~cnt~ vector giống nhau, số cách chọn hai vector là ~cnt(cnt - 1) / 2~, cộng giá trị này vào đáp án.
Mỗi bộ ba thẳng hàng được đếm tại cả 3 điểm nên kết quả cuối cùng chia cho ~3~.
Độ phức tạp: ~O(N^2 log N)~.
Bộ nhớ: ~O(N)~.
Bình luận