【题目描述】 给出平面上一些点(少于50个），坐标都是整数(|xi|,|yi| <= 109)，有可能重复。问存在多少个以这些点为顶点的平行于坐标轴的不同矩形。(两个矩形如果四个顶点坐标都相同，就算相同的矩形) 【输入】 第一行一个整数T(T <= 100)表示测试数据的组数 对于每组数据 第一行一个整数n，表示点的数量 下面n行每行两个整数xi,yi表示点的坐标。 【输出】 T行，每行一个整数表示以这些点为顶点的平行于坐标轴的矩形个数。 【输入样例】 1 7 0 0 0 1 0 2 1 0 1 1 1 2 0 0 【输出样例】 3 【提示】 直接穷举即可。

算法1

(暴力枚举) $O(n^4)$

枚举每个矩形的对角线顶点，并检查对角线上是否有点即可。

时间复杂度

暴力枚举每个矩形的对角线顶点，时间复杂度 $O(n^4)$。

C++ 代码

算法2

(次暴力枚举) $O(n^3)$

枚举每个矩形左上角和右下角的点，检查另外两个点是否存在即可。为了方便查找，可以将所有点放到一个 set 中。

时间复杂度

由于用了 set，查找时间复杂度 $O(\log n)$，故总时间复杂度为 $O(n^3 \log n)$。

C++ 代码

算法3

(暴力枚举+离散化) $O(n^3)$

还是枚举每个矩形左上角和右下角的点，检查另外两个点是否存在。为了方便检查，可以对所有点的坐标进行离散化，把点的坐标从 $[-10^9, 10^9]$ 映射到 $[0, n]$，使得坐标差距不是特别大，可以通过数组朴素方式来访问并保存。

时间复杂度

由于对坐标进行了离散化，故查找时间复杂度近似为 $O(1)$，故总时间复杂度为 $O(n^3)$。

C++ 代码

算法4

(暴力枚举+map) $O(n^3 \log n)$

还是枚举每个矩形左上角和右下角的点，检查另外两个点是否存在。为了方便查找，可以把所有点放到一个 map 中，以点坐标为 key，以点出现的次数为 value。

时间复杂度

由于用了 map，查找时间复杂度 $O(\log n)$，故总时间复杂度为 $O(n^3 \log n)$。

C++ 代码