Problem
https://vn.spoj.com/problems/VOSRTRI
https://oj.vnoi.info/problem/VOSRTRI
Cho N điểm trên mặt phẳng tọa độ. Yêu cầu đếm số tam giác vuông có cạnh bên song song với trục Ox và Oy trên trục tọa độ Oxy.
- Dòng đầu tiên chứa
N
là số lượng điểm trên mặt phẳng tọa độ. N
dòng tiếp theo, mỗi dòng miêu tả tọa độ của một điểm trong N
điểm trên.- Lưu ý: dữ liệu đảm bảo không có 2 điểm trùng nhau.
Output
- Một dòng chứa kết quả bài toán.
Ràng buộc
N <= 100,000
.1 <= X, Y <= 100,000
.
Ví dụ
Input
6
10 10
20 10
10 20
20 20
30 20
30 30
Output
8
Ảnh minh họa cho 6 điểm trong ví dụ
Tutorial
Nhận xét rằng 1 tam giác thỏa đề chỉ có 1 điểm nằm ngay góc vuông (2 cạnh song song 2 trục Ox, Oy). Do đó chỉ cần đếm số điểm nằm trên 2 trục Ox, Oy của từng điểm, từ đó biết được số tam giác vuông có góc vuông tại điểm đang xét.
Do giới hạn tọa độ là nhỏ nên việc đếm xử lý dễ dàng.
Độ phức tạp O(N)
Submission
Nếu bạn thấy bài viết này hay, hãy share bài viết này cho mọi người nhé 😉.
Share this post →