AT_abc131_f.[ABC131F] Must Be Rectangular!

提高+/省选-

通过率:0%

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

在二维平面上有 NN 个点,第 ii 个点的坐标为 (xi,yi)(x_i, y_i)

你可以重复进行如下操作,直到无法继续为止:

  • 选择整数 a,b,c,d (ac,bd)a, b, c, d\ (a \neq c, b \neq d),使得在坐标 (a,b),(a,d),(c,b),(c,d)(a, b), (a, d), (c, b), (c, d) 中恰好有 33 个点已经存在,然后在剩下的 11 个位置添加一个点。

可以证明,这个操作最多只能进行有限次。请你求出最多可以进行多少次操作。

输入格式

输入以如下格式从标准输入读入:

NN x1x_1 y1y_1 :: xNx_N yNy_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

说明/提示

限制条件

  • 1N1051 \leq N \leq 10^5
  • 1xi,yi1051 \leq x_i, y_i \leq 10^5
  • 对于任意 iji \neq j,有 xixjx_i \neq x_jyiyjy_i \neq y_j
  • 输入均为整数

样例解释 1

a=1,b=1,c=5,d=5a = 1, b = 1, c = 5, d = 5 时,可以在 (1,5)(1, 5) 处添加一个点。此后无法再进行操作,所以最大操作次数为 11 次。

样例解释 2

只有 22 个点,无法进行任何一次操作。

样例解释 3

对于所有 a=1,b=1,c=i,d=j (2i,j5)a = 1, b = 1, c = i, d = j\ (2 \leq i, j \leq 5),都可以进行操作,且之后无法再进行操作,所以最大操作次数为 1616 次。

首页