题目描述

难度分:$1400$

输入$n(1 \leq n \leq 2 \times 10^5)$和平面直角坐标系上的$n$个点，横纵坐标范围$[-10^9,10^9]$。

有多少个$(i,j)$满足$i \lt j$且点$i$到点$j$的曼哈顿距离和欧式距离相等？

注意：可能有重复的点。

输入样例$1$

3
1 1
7 5
1 5

输出样例$1$

2

输入样例$2$

6
0 0
0 1
0 2
-1 1
0 1
1 1

输出样例$2$

11

算法

分析性质+哈希表统计

设任意两点$(x_1,y_1)$和$(x_2,y_2)$，$dx=|x_1-x_2|$，$dy=|y_1-y_2|$。将题目中的约束转化成表达式，则有$\sqrt{dx^2+dy^2}=|dx|+|dy|$，很容易发现要想满足这个，那$dx$和$dy$必须有一个是$0$。

所以利用哈希表进行统计，$xcnt$统计横坐标相同的点数，$ycnt$统计纵坐标相同的点数。分别从横坐标、纵坐标相同的点里面选择两个点都能满足欧氏距离等于曼哈顿距离。

但需要注意的是题目中给出的$n$个点可能存在重复，这样重复的点会在以上两次统计中被重复统计，所以把这些重复统计的部分减掉才能得到答案。因此，还需要一个哈希表$counter$，用来统计所有坐标的出现频率，$key$为坐标二元组$(x,y)$，$value$为频数。

复杂度分析

时间复杂度

遍历$n$个点预处理出三个哈希表$xcnt$、$ycnt$和$counter$。然后再分别遍历三个哈希表计算答案即可，时间复杂度为$O(n)$。代码实现的时候懒得写$counter$的哈希函数，直接用的有序表，因此本代码的时间复杂度是$O(log_2n)$。

空间复杂度

空间消耗就是这三个表的空间，在最坏情况下它们都有$O(n)$级别的键值对，因此额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <map>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

int n, x, y;

int main() {
    scanf("%d", &n);
    map<PII, LL> counter;
    unordered_map<int, LL> xcnt, ycnt;
    for(int i = 1; i <= n; i++) {
        scanf("%d%d", &x, &y);
        xcnt[x]++;
        ycnt[y]++;
        counter[{x, y}]++;
    }
    LL ans = 0;
    for(auto&[_, v]: xcnt) {
        ans += v*(v - 1)/2;
    }
    for(auto&[_, v]: ycnt) {
        ans += v*(v - 1)/2;
    }
    for(auto&[_, v]: counter) {
        ans -= v*(v - 1)/2;
    }
    printf("%lld\n", ans);
    return 0;
}