ei1903の競プロメモ

競プロの解説など

HOJ 1525 - Counting Squares

HOJ 解説

問題概要

二次元座標平面上に $\ N \$ 個の点があり、 $i \$ 番目の点の座標は $\ (x_i,y_i) \$ である。
次の条件を満たす整数 $\ i,j \$ の組の個数を求めよ。

$1 \leq i \lt j \leq N$
四角形 $\ (x_i,y_i),(x_i,y_j),(x_j,y_j),(x_j,y_i) \$ は正方形である。

制約

$2 \leq N \leq 3 \times 10^5$
$-10^9 \leq x_i,y_i \leq 10^9$
$(x_i,y_i) \neq (x_j,y_j) \ (i \neq j)$

解説

整数 $\ i,j \ (i \lt j) \$ が条件を満たすとき以下のことが成り立ちます。

$x_i + y_i = x_j + y_j \$ または $\ x_i - y_i = x_j - y_j$

よって、上記の条件を満たすペアを数え上げればよいです。これは求めた値をソートし連続する同じ値の個数から求める方法や、C++ならばstd::mapを使う方法があります。