题目描述
在一个二维平面上有 N 个点。第 i 个点的坐标是(xi,yi)。
我们要尽可能多地执行以下操作:
- 选择四个整数 a,b,c,d(a=c,b=d),使得位置(a,b)、(a,d)、(c,b)和(c,d)中有恰好三个点,并在剩下的位置上添加一个点。
我们可以证明,这个操作只能执行有限次数。找到我们能执行的操作的最大次数。
输入
第一行一个整数N
接下来一共N行,表示每个点的点对。
输出
输出可以执行的操作的最大次数。
3
1 1
5 1
5 5
1
样例解释
通过选择a=1,b=1,c=5,d=5,我们可以在位置(1,5)添加一个点。我们不能再执行这个操作了,所以最大操作次数为 1。
2
10 10
20 20
0
样例解释
只有两个点,所以我们根本不能执行这个操作。
9
1 1
2 1
3 1
4 1
5 1
1 2
1 3
1 4
1 5
16
样例解释
我们可以在所有形如a=1,b=1,c=i,d=j(2<i,j<5)的选择上进行操作,但不能再多了。
因此,最大操作次数为 16。
提示
1≤N≤105
1≤xi,yi≤105
对于i=j,xi=xj或yi=yj