【2017集训选拔赛】Rectangle Recognition

时间限制: 6000 ms 内存限制: 131072 kb
总通过人数: 1 总提交人数: 1

题目描述

给定二维平面上的 $n$ 个互异的整点,我们需要你从中选出恰好 $4$ 个互异的点形成与坐标轴平行的矩形,请你计算有多少种选取方式。

输入

第一行包含一个正整数 $T$ ,表示有 $T$ 组测试数据。

接下来依次给出每组测试数据。对于每组测试数据:

第一行包含一个整数 $n$ ,表示平面上整点的数量。

接下来 $n$ 行,每行包含两个整数 $x$ 和 $y$ ,表示 $(x, y)$ 处有一个点。

保证所有的点坐标互不相同,输入数据不超过 30 MB

$1 \leq T \leq 20, 1 \leq n \leq 10^5, -10^9 \leq x, y \leq 10^9$

输出

对于每组数据输出一行,包含一个整数,表示选取方式的数量。

注意:$\displaystyle{10^5 \choose 4} \leq 2^{63} - 1$

输入样例

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

输出样例

3

样例解释

对于第一组数据,3 个矩形分别为 $[0, 1] \times [0, 1],$ $[0, 1] \times [0, 2],$ $[0, 1] \times [1, 2]$ 。

相关推荐