問題概要
二次元座標平面上に$ \ 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を使う方法があります。
