Codeforces Round #345 (Div. 1) A. Watchmen
解法
マンハッタン距離とユークリッド距離が一致するのは, 「x 座標または y 座標が一致する時」です。
X[x] = (x 座標が x の点の数), Y[y] = (y 座標が y の点の数) を数えておけば, 基本的には C[X[x]][2], C[Y[y]][2] の和が答えになります。(C はコンビネーションを指す)
ですが, 同じ点の座標はダブって数えてしまっているので, これは引いて置かなければなりません。その数は XY[(x, y)] (x 座標が x で y 座標が y の点の数)を数えておけば, C[XY[(x, y)]][2] の和を引くことになります。
int main() { cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; map<int, ll> X, Y; map<pii, ll> XY; for (int i = 0; i < n; i++) { int x, y; cin >> x >> y; X[x]++; Y[y]++; XY[pii(x, y)]++; } ll ans = 0; for (auto p : X) ans += (p.second-1)*p.second/2; for (auto p : Y) ans += (p.second-1)*p.second/2; for (auto p : XY) ans -= (p.second-1)*p.second/2; cout << ans << endl; return 0; }