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)$ 中恰好有三个位置有点，然后在剩下的位置上添加一个点。

我们可以证明这种操作只能执行有限次。求最多可以执行多少次该操作。

输入格式

输入格式（标准输入）如下： $N$ $x_1$ $y_1$ : $x_N$ $y_N$

输出格式

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

3
1 1
5 1
5 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

提示

$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$。 输入中的所有数值均为整数。通过选择 $a = 1$, $b = 1$, $c = 5$, $d = 5$，我们可以在 $(1, 5)$ 添加一个点。之后无法再进行操作，因此操作的最大次数为 $1$。
只有两个点，所以无法进行任何操作。
对于所有形如 $a = 1$, $b = 1$, $c = i$, $d = j$ $(2 \leq i,j \leq 5)$ 的选择，我们都可以进行操作，且没有更多可能。因此操作的最大次数为 $16$。

标签: AtCoder|abc131F

来源

AtCoder|abc131F