CodeForces 651C – Watchmen [规律+容斥]

Link

传送门

Problem

Watchmen are in a danger and Doctor Manhattan together with his friend Daniel Dreiberg should warn them as soon as possible. There are n watchmen on a plane, the i-th watchman is located at point (xi, yi).

They need to arrange a plan, but there are some difficulties on their way. As you know, Doctor Manhattan considers the distance between watchmen i and j to be |xi - xj| + |yi - yj|. Daniel, as an ordinary person, calculates the distance using the formula .

The success of the operation relies on the number of pairs (i, j) (1 ≤ i < j ≤ n), such that the distance between watchman i and watchmen j calculated by Doctor Manhattan is equal to the distance between them calculated by Daniel. You were asked to compute the number of such pairs.

The first line of the input contains the single integer n (1 ≤ n ≤ 200 000) — the number of watchmen.

Each of the following n lines contains two integers xi and yi (|xi|, |yi| ≤ 109).

Some positions may coincide.

Print the number of pairs of watchmen such that the distance between them calculated by Doctor Manhattan is equal to the distance calculated by Daniel.

Mean

有N个点,求有多少对点,他们的欧几里得距离==曼哈顿距离。

Analysis

首先两点重合或者在坐标同一行或同一列时,两个距离相同。那么用map分别保存X轴和Y轴相同点的个数。最后重合点算了两遍,所以需要减掉。

这几次cf每次都掉链子…这次开了long long但是只有一个关键地方没用long long,被人hack了……

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;

map<ll, ll> cntX, cntY;
map<P, ll> cnt;

int main() {
    ios::sync_with_stdio(false);
    int n; cin >> n;
    for (int i = 0; i < n; ++i) {
        ll x, y; cin >> x >> y;
        ++cntX[x];
        ++cntY[y];
        ++cnt[P(x, y)];
    }
    ll ans = 0;
    for(auto i : cntX)
        ans += (i.second * (i.second - 1)) / 2;
    for(auto i : cntY)
        ans += (i.second * (i.second - 1)) / 2;
    for(auto i : cnt)
        ans -= (i.second * (i.second - 1)) / 2;
    cout << ans << endl;
    return 0;
}

欢迎留言