#AT1136. 必须是矩形!

必须是矩形!

题目描述

在一个二维平面上有 NN 个点。第 ii 个点的坐标是(xi,yi)(x_i,y_i)

我们要尽可能多地执行以下操作:

  • 选择四个整数 a,b,c,d(ac,bd)a,b,c,d(a ≠ c,b≠ d),使得位置(a,b)(a,d)(c,b)(c,d)(a, b)、(a, d)、(c,b)和(c,d)中有恰好三个点,并在剩下的位置上添加一个点。

我们可以证明,这个操作只能执行有限次数。找到我们能执行的操作的最大次数。

输入

第一行一个整数NN

接下来一共NN行,表示每个点的点对。

输出

输出可以执行的操作的最大次数。

3
1 1
5 1
5 5
1

样例解释

通过选择a=1,b=1,c=5,d=5a= 1,b= 1,c= 5,d=5,我们可以在位置(1,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)a= 1,b= 1,c=i,d=j(2<i,j<5)的选择上进行操作,但不能再多了。

因此,最大操作次数为 16。

提示

1N105 1 \leq N \leq 10^5

1xi,yi1051 \leq x_i,y_i \leq 10^5

对于ij,xixjyiyj对于 i \neq j, x_i \neq x_j 或 y_i \neq y_j