Giải cứu đàn gà

View as PDF



Problem type
Points: 10 (p) Time limit: 1.0s Memory limit: 100M Input: stdin Output: stdout

Đà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ác 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 độ Decac 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 \leq i, j \leq 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}| \leq 10 ^ 9)\) là tọa độ của con gà thứ \(i\).

Kết quả ra:

  • 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.
Ví dụ 1:
INPUT
3
1 1
7 5
1 5
OUTPUT
2
Ví dụ 2:
INPUT
6
0 0
0 1
0 2
-1 1
0 1
1 1
OUTPUT
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) Ràng buộc:

Giới hạn:

  • Thời gian: 1s/test
  • Subtask 1: 50% số test đầu tiên \(N \leq 500\)
  • \(2 \leq N \leq 10 ^ 6 |x_{i}|, |y_{i}| \leq 10 ^ 9\)
  • Subtask 2: 30% số test tiếp theo \(N \leq 100\)
  • Subtask 3: 20% số test cuối cùng không có ràng buộc gì thêm

Comments


  • 0
    nhatnamst8a    Feb. 20, 2024, 8:34 p.m.

    tr má ô inp,out load k kịp=)