加班狗:军团(c++,算法,哈希表)

土豆游戏公司最新3A大作《加班狗:军团》发售啦!

本作设定在赛博朋克风格的虚构未来都市鹅城。鹅城被堕落的资本垄断巨头所掌控,腐败的北山法院强行通过了无限制加班法,迫使所有平民变成加班狗,为强大的剥削集团贡献出所有剩余价值。玩家的任务就是组建力量反抗压迫。

本作的特色在于玩家能够完全自由地去“扮演任何一个人”。鹅城的每一个市民都是完全拟真的、拥有日常生活和背景故事的个体,而玩家可以从市民中招募任何人成为队友并进行扮演。从点到为止的太极大师到不讲武德的健身达人,任何人都能加入抵抗组织成为觉醒的打工人。

游戏上线后,玩家们都对其创新玩法十分感兴趣,但可惜的是,由于土豆游戏公司企业文化的传统艺能,《加班狗:军团》在发售几天后就出现了恶性BUG——队友的坐标距离计算系统在特定情况下会出现异常。

由原本的欧氏距离 √(xi−xj)2+(yi−yj)2

变成曼哈顿距离 |xi−xj|+|yi−yj|

玩家群体之间流传着该BUG十分诡异的传说,据说只有在角色吃掉一万个土豆的情况下才有概率发生,但开发组却一直找不到具体成因,因此需要立即收集错误信息进行研究。已知每次可能出现BUG的距离计算都是在某一对坐标间发生的,所以可以先把无法确定是否发生异常的坐标对筛选出来,以尽量缩小排查错误的范围。

于是你作为土豆游戏公司的加班程序员被分配到了这个紧急任务——统计不管是否发生异常,距离计算结果都一样,即欧氏距离和曼哈顿距离相同的坐标对的数量。
输入数据

第一行输入是一个整数 Q (1 ≤ Q ≤ 10),表示总共有 Q 组数据。

对于每组数据,第一行输入是一个整数 n (1 ≤ n ≤ 200,000),表示目前游戏中有 n 位队友。

接下来的 n 行,每行包括两个整数 xi 和 yi (| xi |, | yi | ≤ 10^9),表示每位队友的坐标。同样由于土豆游戏公司的传统艺能,游戏角色之间可能发生穿模,因此坐标可能重合。

保证Q 组数据中n 的总和不超过 200,000,

输出数据

输出不管是否发生异常,距离计算结果都一样,即欧氏距离和曼哈顿距离相同的坐标对的数量。每组样例之间用回车隔开
输入:
2
3
1 1
7 5
1 5
6
0 0
0 1
0 2
-1 1
0 1
1 1

输出:
2
11