trang chủ / bài tập / 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 ij, ta xét hai cách tính khoảng cách:

  • Khoảng cách Manhattan: |xixj|+|yiyj|.
  • Khoảng cách Euclid: (xixj)2+(yiyj)2.

Hãy đếm số cặp (i,j) với 1i<jn 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 xiyi — 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

  • 1n200000.
  • |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 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+61=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.400 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.2 gforth 0.7.3 gfortran 12.2.0 go 1.27.0 groovyc 5.1.1 javac 25.0.4 node 26.8.1 julia 1.12.7 kotlinc 2.4.10 lean 4.33.1 sbcl 2.2.9 lua 5.4.9 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.10 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.14.7 racket 8.7 ruby 4.0.6 rustc 1.98.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.3.3 tclsh 8.6 bun 1.4.0 deno 2.9.6 v 0.5.2 zig 0.16.0