分数: 600 点
问题陈述
有 N 二维平面中的点。的坐标 i第一个点是 (x_i, y_i).
我们将尽可能长时间地重复以下操作:
- 选择四个整数 a, b, c, d (a \neq c, b \neq d) 使得正好三个位置有点 (a, b), (a, d), (c, b) 和 (c, d),并在剩余位置添加一个点。
我们可以证明我们只能执行有限次这个操作。求我们可以执行该操作的最大次数。
约束
- 1 \leq N \leq 10^5
- 1 \leq x_i, y_i \leq 10^5
- If i \neq j, x_i \neq x_j or y_i \neq y_j.
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N x_1 y_1 : x_N y_N
输出
打印我们可以执行该操作的最大次数。
示例输入 1
3 1 1 5 1 5 5
示例输出 1
1
通过选择 a = 1, b = 1, c = 5, d = 5,我们可以在 (1, 5)。我们不能再进行操作了,所以最大操作次数是 1.
示例输入 2
2 10 10 20 20
示例输出 2
0
只有两个点,所以我们根本无法进行操作。
示例输入 3
9 1 1 2 1 3 1 4 1 5 1 1 2 1 3 1 4 1 5
示例输出 3
16
我们可以对表单的所有选择进行操作 a = 1, b = 1, c = i, d = j (2 \leq i,j \leq 5),仅此而已。因此,最大操作次数为 16.