trang chủ / đề bài / icpc21_mn_o

Watchmen

Đề bài

Mô tả

Các Watchmen đang gặp nguy hiểm và Doctor Manhattan cùng người bạn Daniel Dreiberg cần cảnh báo cho họ càng sớm càng tốt. Có n Watchmen trên mặt phẳng, người thứ i ở điểm (xi,yi).

Họ cần lập một kế hoạch, nhưng có vài khó khăn trên đường. Như bạn biết, Doctor Manhattan coi khoảng cách giữa hai Watchmen i và j là |xi−xj|+|yi−yj|. Còn Daniel, là một người bình thường, tính khoảng cách theo công thức (xi−xj)2+(yi−yj)2.

Sự thành công của chiến dịch phụ thuộc vào số cặp (i,j) (1≤i<j≤n) mà khoảng cách giữa Watchman i và Watchman j do Doctor Manhattan tính bằng khoảng cách do Daniel tính.

Yêu cầu: Hãy đếm số cặp như vậy.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên n: số Watchmen.
  • Mỗi dòng trong n dòng tiếp theo chứa hai số nguyên xi và yi.

Dữ liệu ra

In ra số cặp Watchmen mà khoảng cách do Doctor Manhattan tính bằng khoảng cách do Daniel tính.

Ràng buộc

  • 1≤n≤200000.
  • |xi|,|yi|≤109.

Ví dụ

Input Output Giải thích
3
1 1
7 5
1 5
2 Với Watchman 1 và 2, Doctor Manhattan tính được |1−7|+|1−5|=10, còn Daniel tính được (1−7)2+(1−5)2=213. Với các cặp (1,1),(1,5) và (7,5),(1,5), hai người tính ra cùng một khoảng cách.
6
0 0
0 1
0 2
-1 1
0 1
1 1
11

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0