测评会员优惠活动进行中 · 开通 VIP,有效期内测评不限次 VIP 优惠中 · 测评不限次 立即查看

A7643. [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
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

说明/提示

## 限制条件

- $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$ 次。
上一题 去做题 下一题