Teleportation

题目描述

亚托德计算平面共和国（The Republic of AtCoder）位于笛卡尔坐标平面上。
该国有 $N$ 个城镇，编号为 $1,2,\dots,N$。城镇 $i$ 位于 $(x_i, y_i)$，且任意两个不同的城镇的坐标都不相同。 该国有瞬间移动魔法（teleportation spells）。一个法术由一对整数 $(a,b)$ 标识，在坐标 $(x, y)$ 处施放法术 $(a, b)$ 会把你传送到 $(x+a, y+b)$。 Snuke 是一位伟大的魔法师，他可以学习任意一对整数 $(a, b)$ 所对应的法术。可学习的法术数量也没有上限。
为了能够使用法术在各城镇之间移动，他决定学习若干法术，使得对于每一对不同的城镇 $(i, j)$ 都能够做到以下要求。

在所学法术中为每一对不同城镇 $(i,j)$ 选择仅一个法术。然后，仅重复使用所选的该一个法术多次，从城镇 $i$ 到达城镇 $j$。

问为了实现上述目标，Snuke 至少需要学习多少个法术？

输入格式

输入由标准输入给出，格式如下： $N$ $x_1$ $y_1$ $x_2$ $y_2$ $\vdots$ $x_N$ $y_N$

输出格式

输出 Snuke 需要学习的最少法术数量。

3
1 2
3 6
7 4

6

3
1 2
2 2
4 2

2

4
0 0
0 1000000000
1000000000 0
1000000000 1000000000

8

提示

$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$。下图展示了城镇的位置（以及四个角点的坐标）。 如果 Snuke 学习下面这六个法术，则对于每一对 $(i,j)$ $(i \neq j)$，他可以通过对其中某个法术使用一次从城镇 $i$ 到达城镇 $j$，从而满足要求。

$(2, 4)$ $(-2, -4)$ $(4, -2)$ $(-4, 2)$ $(-6, -2)$ $(6, 2)$

另一种选择是学习下面这六个法术。在这种情况下，对于每一对 $(i,j)$ $(i \neq j)$，他可以通过对其中某个法术使用两次从城镇 $i$ 到达城镇 $j$，从而满足要求。

$(1, 2)$ $(-1, -2)$ $(2, -1)$ $(-2, 1)$ $(-3, -1)$ $(3, 1)$

不存在由少于六个法术构成的组合能够实现该目标，因此我们应输出 $6$。
最优选择是学习下面两个法术：

$(1, 0)$ $(-1, 0)$

标签: AtCoder|abc226D

来源

AtCoder|abc226D