AT_nyc2015_12.机のしみ

输入以如下格式从标准输入中给出。

$N$
$x_1\ y_1$
$\vdots$
$x_N\ y_N$

请将答案输出在一行中。

例如：

3
1 5
3 6
4 9

输出：

6

第一行为一个整数 $N$，表示已有的“污点”数量。
接下来的 $N$ 行，每行包含两个整数 $x_i$ 和 $y_i$，表示第 $i$ 个污点的坐标。

输出一个整数，表示需要额外添加的最少污点数量。

数据范围

• すぬけ君的桌子上有 $N$ 个污点，第 $i$ 个污点的坐标为 $(x_i, y_i)$。

• すぬけ君希望通过添加若干（可以为 $0$ 个）污点，使得所有污点整体能够构成一个棋盘。棋盘的定义为：存在某个 $K$，使得 $K^2$ 个污点排列成 $K \times K$ 的正方形网格。注意，棋盘不要求与坐标轴平行。

• 请你求出最少需要添加多少个污点。

• 假设桌子的面积足够大，不会出现污点超出桌面范围的情况。

• 输入的坐标均为整数，但新添加的污点坐标可以不是整数。

• $1 \leq N \leq 100000$

• $0 \leq x_i, y_i \leq 10^9$

• 不存在两个污点在同一坐标

• 所有输入均为整数

由 ChatGPT 4.1 翻译