AT_abc131_f [ABC131F] Must Be Rectangular!

题目描述

在二维平面上有 $N$ 个点，第 $i$ 个点的坐标为 $(x_i, y_i)$。

你可以重复进行如下操作，直到无法继续为止：

• 选择整数 $a, b, c, d\ (a \neq c, b \neq d)$，使得在坐标 $(a, b), (a, d), (c, b), (c, d)$ 中恰好有 $3$ 个点已经存在，然后在剩下的 $1$ 个位置添加一个点。

可以证明，这个操作最多只能进行有限次。请你求出最多可以进行多少次操作。

输入格式

输入以如下格式从标准输入读入：

$N$ $x_1$ $y_1$ $:$ $x_N$ $y_N$

输出格式

输出最多可以进行的操作次数。

样例 1

输入

3
1 1
5 1
5 5

输出

1

样例 2

输入

2
10 10
20 20

输出

0

样例 3

输入

9
1 1
2 1
3 1
4 1
5 1
1 2
1 3
1 4
1 5

输出

16

说明/提示

限制条件

• $1 \leq N \leq 10^5$
• $1 \leq x_i, y_i \leq 10^5$
• 对于任意 $i \neq j$，有 $x_i \neq x_j$ 或 $y_i \neq y_j$
• 输入均为整数

样例解释 1

当 $a = 1, b = 1, c = 5, d = 5$ 时，可以在 $(1, 5)$ 处添加一个点。此后无法再进行操作，所以最大操作次数为 $1$ 次。

样例解释 2

只有 $2$ 个点，无法进行任何一次操作。

样例解释 3

对于所有 $a = 1, b = 1, c = i, d = j\ (2 \leq i, j \leq 5)$，都可以进行操作，且之后无法再进行操作，所以最大操作次数为 $16$ 次。

由 ChatGPT 4.1 翻译