D - Teleportation
当前没有测试数据。
D - 传送
得分：400分
问题描述
AtCoder 共和国位于平面直角坐标系上。
它有$N$座城镇，编号为$1,2,\dots,N$。第$i$座城镇位于$(x_i, y_i)$处，且没有两座不同的城镇位于相同的坐标。
这个国家有传送咒语。咒语由一对整数$(a,b)$确定，使用咒语$(a, b)$时，将你传送到$(x+a, y+b)$处。
Snuke 是一位了不起的魔法师，他可以任意选择一对整数$(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)$
- 如果 $i \neq j$ ，则 $(x_i, y_i) \neq (x_j, y_j)$。
输入
输入在标准输入中以下述格式给出：
输出
输出需要 Snuke 学习的最小咒语数量。
3
1 2
3 6
7 4
6
下图显示了城镇的位置（包括四个角落的坐标）。
如果 Snuke 学习以下六个咒语，他可以对于每一对 $(i,j)$（$i \neq j$），使用其中一个咒语一次以实现他的目标。
- $(2, 4)$
- $(-2, -4)$
- $(4, -2)$
- $(-4, 2)$
- $(-6, -2)$
- $(6, 2)$
另一种选择是学习以下六个咒语。在这种情况下，他可以对于每一对 $(i,j)$（$i \neq j$），使用其中一个咒语两次以实现他的目标。
- $(1, 2)$
- $(-1, -2)$
- $(2, -1)$
- $(-2, 1)$
- $(-3, -1)$
- $(3, 1)$
不存在由少于六个咒语组成，且能实现目标的组合，所以输出结果为$6$。
3
1 2
2 2
4 2
2
最优选择是学习以下两个咒语：
- $(1, 0)$
- $(-1, 0)$
4
0 0
0 1000000000
1000000000 0
1000000000 1000000000
8