mayoko’s diary

プロコンとかいろいろ。

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;
}