Độ khó: Trung bình (2/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Bài 2. Giải cứu đàn gà (GV ra đề: Vương Thành Trung)

Đàn gà con đang gặp nguy hiểm trước sự tấn công của lũ quạ, Bờm và Cuội phải tìm cách giải cứu chúng ngay lập tức. Có tổng cộng ~N~ con gà đang đứng nháo nhác trên một hệ trục tọa độ Descartes ~Oxy~, con gà thứ ~i~ đang đứng ở vị trí tọa độ ~(x_i, y_i)~.

Bờm và Cuội cần có một kế hoạch giải cứu, nhưng những con gà thì lại gặp khó khăn trong quá trình di chuyển của chúng, vì vậy chúng cần phải theo sự hướng dẫn của Bờm và Cuội. Tuy nhiên, Bờm và Cuội lại không thống nhất được cách di chuyển của những con gà của mình: theo Bờm, nếu hai con gà ở vị trí ~(x_i, y_i)~ và vị trí ~(x_j, y_j)~ thì khoảng cách của chúng sẽ là ~|x_i - x_j| + |y_i - y_j|~, còn theo Cuội thì khoảng cách giữa chúng là ~\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}~.

Sự thành công của cuộc giải cứu phụ thuộc vào số cặp ~(i, j)~ ~(1 \le i, j \le N)~ sao cho khoảng cách giữa con gà thứ ~i~ và con gà thứ ~j~ tính theo cách của Bờm bằng với khoảng cách tính theo cách của Cuội. Bạn hãy đếm số lượng cặp gà như vậy.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên ~N~.
• ~N~ dòng tiếp theo, mỗi dòng thứ ~i~ chứa hai số nguyên ~x_i, y_i~ ~(|x_i|, |y_i| \le 10^9)~ là tọa độ của con gà thứ ~i~.

Kết quả

• Số lượng cặp gà thỏa mãn khoảng cách giữa chúng theo cách tính của Bờm bằng khoảng cách theo cách tính của Cuội.

Giới hạn

• ~2 \le N \le 10^6~; ~|x_i|, |y_i| \le 10^9~.
• Subtask 1: 50% số test đầu tiên ~N \le 500~;
• Subtask 2: 30% số test tiếp theo ~N \le 100\,000~;
• Subtask 3: 20% số test cuối cùng không có ràng buộc gì thêm.

Sample Input 1

3
1 1
7 5
1 5

Sample Output 1

2

Sample Input 2

6
0 0
0 1
0 2
-1 1
0 1
1 1

Sample Output 2

11

Giải thích

Ví dụ 1: Có 2 cặp gà thỏa mãn yêu cầu là ~(1, 1)~ và ~(1, 5)~; ~(7, 5)~ và ~(1, 5)~.

Lưu ý: cặp ~(i, j)~ và ~(j, i)~ chỉ tính 1 lần, và không tính cặp một con gà với chính nó (tức là đếm các cặp ~i < j~). Hai con gà đứng trùng chỗ nhau vẫn được tính (khoảng cách theo cả 2 cách đều bằng ~0~).