← 返回题目列表

AtCoder · abc131_f

F. 必须是矩形!

中文机器翻译题面 查看原题

分数: 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.