DISTSUM - Khoảng cách Manhattan

View as PDF

Submit solution

Points: 100.00
Time limit: 1.0s
Memory limit: 1000M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text

Cho n điểm trên mặt phẳng tọa độ Oxy, điểm thứ i có tọa độ (xi,yi). Ta định nghĩa khoảng cách Manhattan giữa hai điểm ij|xixj|+|yiyj|. Hãy tính tổng khoảng cách Manhattan giữa tất cả mọi cặp điểm.

Dữ liệu

  • Dòng đầu tiên gồm số nguyên n (1n100000) - số lượng điểm.
  • n dòng tiếp theo, dòng thứ i gồm hai số nguyên xiyi (108xi,yi108) - tọa độ của điểm thứ i.

Kết quả

  • In ra tổng khoảng cách Manhattan cần tìm.

Ví dụ

Sample Input 1
Copy
3
1 3
-2 3
-2 5
Sample Output 1
Copy
10
Sample Input 2
Copy
2
0 0
0 0
Sample Output 2
Copy
0

Giải thích

Ở ví dụ thứ nhất, ta có:

  • Khoảng cách Manhattan giữa điểm 1 và điểm 2 là: |1 − (−2)| + |3 − 3| = 3
  • Khoảng cách Manhattan giữa điểm 1 và điểm 3 là: |1 − (−2)| + |3 − 5| = 5
  • Khoảng cách Manhattan giữa điểm 2 và điểm 3 là: |(−2) − (−2)| + |3 − 5| = 2

Tổng khoảng cách Manhattan là 3+5+2 = 10.

Giới hạn
  • Subtask 1 (50% số điểm): n1000
  • Subtask 2 (50% số điểm): Không có ràng buộc gì thêm

Nguồn: Free Contest


Comments

Please read the guidelines before commenting.


There are no comments at the moment.