VOSRTRI - Tam giác vuông

Tags: math

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ôngcạnh bên song song với trục OxOy trên trục tọa độ Oxy.

Input

  • 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

VOSRTRI.cpp