「OOI 2016 Day 1」守护者 题解

题目分析

我们有 $n$ 个点 $(x_i, y_i)$，需要找出所有满足曼哈顿距离等于欧几里得距离的点对 $(i, j)$ $(i < j)$。

关键推导

曼哈顿距离：$d_M = |x_i - x_j| + |y_i - y_j|$

欧几里得距离：$d_E = \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}$

要使 $d_M = d_E$，即：

$$|x_i - x_j| + |y_i - y_j| = \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2} $$

两边平方：

$$(|x_i - x_j| + |y_i - y_j|)^2 = (x_i - x_j)^2 + (y_i - y_j)^2 $$

展开左边：

$$|x_i - x_j|^2 + |y_i - y_j|^2 + 2|x_i - x_j||y_i - y_j| = (x_i - x_j)^2 + (y_i - y_j)^2 $$

由于 $|a|^2 = a^2$，两边抵消后得到：

$$2|x_i - x_j||y_i - y_j| = 0$$

因此条件等价于：

$$|x_i - x_j| \cdot |y_i - y_j| = 0$$

即：

$$x_i = x_j \quad \text{或} \quad y_i = y_j$$

计数方法

设：

• $C_x[v]$ 表示横坐标为 $v$ 的点的数量
• $C_y[v]$ 表示纵坐标为 $v$ 的点的数量
• $C_{xy}[(x, y)]$ 表示点 $(x, y)$ 出现的次数

那么：

1. 横坐标相同的点对数量：$\sum_{v} \binom{C_x[v]}{2}$
2. 纵坐标相同的点对数量：$\sum_{v} \binom{C_y[v]}{2}$
3. 完全相同的点对数量：$\sum_{p} \binom{C_{xy}[p]}{2}$

根据容斥原理，最终答案为：

$$\text{答案} = \sum_{v} \binom{C_x[v]}{2} + \sum_{v} \binom{C_y[v]}{2} - \sum_{p} \binom{C_{xy}[p]}{2} $$

复杂度分析

时间复杂度

• 使用 map 存储计数：$O(n \log n)$
• 使用 unordered_map 存储计数：$O(n)$（平均情况）

空间复杂度

• $O(n)$，需要存储各坐标的出现频率

代码实现

#include <iostream>
#include <map>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    map<int, int> countX, countY;
    map<pair<int, int>, int> countXY;

    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        countX[x]++;
        countY[y]++;
        countXY[{x, y}]++;
    }

    long long ans = 0;

    for (auto& p : countX) {
        long long c = p.second;
        ans += c * (c - 1) / 2;
    }

    for (auto& p : countY) {
        long long c = p.second;
        ans += c * (c - 1) / 2;
    }

    for (auto& p : countXY) {
        long long c = p.second;
        ans -= c * (c - 1) / 2;
    }

    cout << ans << "\n";

    return 0;
}

总结

本题的关键在于通过数学推导将距离相等条件转化为坐标相等条件，然后使用组合计数和容斥原理高效解决问题。算法在 $n \leq 2 \times 10^5$ 的数据规模下可以高效运行。