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.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0