分数: 400 点
问题陈述
AtCoder 共和国位于笛卡尔坐标平面上。
它有 N 城镇,编号 1,2,\dots,N。镇 i 位于 (x_i, y_i),并且没有两个不同的城镇位于同一坐标。
这个国家有传送法术。咒语由一对整数来标识 (a,b),并施展咒语 坐标 (a, b) 在坐标处 (x, y) 将你传送到 (x+a, y+b).
Snuke是一位伟大的魔法师,可以学习咒语 (a, b) 对于任何整数对 (a, b) 他的选择。他可以学习的法术数量也是无限的。
为了能够使用法术在城镇之间旅行,他决定学习一定数量的法术,以便可以对每对不同的城镇执行以下操作 (i, j).
- 选择 只需一个咒语 在所学的法术之中。然后反复使用 只是 从城镇获得的所选咒语 i 到镇 j.
Snuke至少需要学习多少法术才能达到上述目标?
约束
- 2 \leq N \leq 500
- 0 \leq x_i \leq 10^9 (1 \leq i \leq N)
- 0 \leq y_i \leq 10^9 (1 \leq i \leq N)
- (x_i, y_i) \neq (x_j, y_j) if i \neq j.
输入
输入由标准输入按以下格式给出:
N x_1 y_1 x_2 y_2 \vdots x_N y_N
输出
打印 Snuke 需要学习的最少法术数量。
示例输入 1
3 1 2 3 6 7 4
示例输出 1
6
下图显示了城镇的位置(以及四个角的坐标)。

如果斯努克学习了以下六个咒语,他可以从城镇中获得 i 到镇 j 每对使用其中一个法术一次 (i,j) (i \neq j),实现了他的目标。
- (2, 4)
- (-2, -4)
- (4, -2)
- (-4, 2)
- (-6, -2)
- (6, 2)
另一种选择是学习以下六个咒语。在这种情况下,他可以从 Town i 到镇 j 每对使用其中一个法术两次 (i,j) (i \neq j),实现了他的目标。
- (1, 2)
- (-1, -2)
- (2, -1)
- (-2, 1)
- (-3, -1)
- (3, 1)
没有少于六个咒语的咒语组合可以实现目标,因此我们应该打印 6.
示例输入 2
3 1 2 2 2 4 2
示例输出 2
2
最佳选择是学习以下两个法术:
- (1, 0)
- (-1, 0)
示例输入 3
4 0 0 0 1000000000 1000000000 0 1000000000 1000000000
示例输出 3
8