AT_abc131_f.[ABC131F] Must Be Rectangular!
提高+/省选-
通过率:0%
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
在二维平面上有 N 个点,第 i 个点的坐标为 (xi,yi)。
你可以重复进行如下操作,直到无法继续为止:
- 选择整数 a,b,c,d (a=c,b=d),使得在坐标 (a,b),(a,d),(c,b),(c,d) 中恰好有 3 个点已经存在,然后在剩下的 1 个位置添加一个点。
可以证明,这个操作最多只能进行有限次。请你求出最多可以进行多少次操作。
输入格式
输入以如下格式从标准输入读入:
N x1 y1 : xN yN
输出格式
输出最多可以进行的操作次数。
输入输出样例
输入#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≤N≤105
- 1≤xi,yi≤105
- 对于任意 i=j,有 xi=xj 或 yi=yj
- 输入均为整数
样例解释 1
当 a=1,b=1,c=5,d=5 时,可以在 (1,5) 处添加一个点。此后无法再进行操作,所以最大操作次数为 1 次。
样例解释 2
只有 2 个点,无法进行任何一次操作。
样例解释 3
对于所有 a=1,b=1,c=i,d=j (2≤i,j≤5),都可以进行操作,且之后无法再进行操作,所以最大操作次数为 16 次。