← 返回题目列表

AtCoder · nyc2015_12

L. 桌子污渍

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

问题陈述

在须拔君的桌子上 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
  • 不会有两个污渍位于相同的坐标。
  • 输入中的所有值都是整数。

输入格式

输入是按以下格式从标准输入给出的。
N
x_1 y_1
:
x_N y_N

输出格式

将答案输出到一行中。

示例输入 1

3
1 5
3 6
4 9

示例输出 1

6
例如,(5, 7), (0, 7), (2, 8), (-1, 9), (1, 10), (3, 11) 只需在六个位置添加污渍即可。