trang chủ / đề bài / watchmen

Watchmen

Đề bài

Mô tả

Cho n điểm trên mặt phẳng tọa độ; điểm thứ i có tọa độ (xi,yi). Một số điểm có thể trùng nhau.

Với hai điểm i và j, ta xét hai cách tính khoảng cách:

  • Khoảng cách Manhattan: |xi−xj|+|yi−yj|.
  • Khoảng cách Euclid: (xi−xj)2+(yi−yj)2.

Hãy đếm số cặp (i,j) với 1≤i<j≤n sao cho khoảng cách Manhattan giữa hai điểm này bằng khoảng cách Euclid.

Dữ liệu vào

  • Dòng đầu chứa số nguyên n — số lượng điểm.
  • n dòng tiếp theo, mỗi dòng chứa hai số nguyên xi và yi — tọa độ điểm thứ i.

Dữ liệu ra

In ra một số nguyên duy nhất — số cặp (i,j) thỏa mãn điều kiện đề bài.

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 Hai cặp thỏa mãn là (1,3) (cùng x=1) và (2,3) (cùng y=5).
6
0 0
0 1
0 2
-1 1
0 1
1 1
11 Có 4 điểm cùng x=0 đóng góp (42)=6 cặp; 4 điểm cùng y=1 đóng góp (42)=6 cặp. Cặp điểm trùng nhau (0,1) bị đếm hai lần nên trừ đi 1, được 6+6−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