102263: [AtCoder]ABC226 D - Teleportation

Problem Statement

The Republic of AtCoder lies on a Cartesian coordinate plane.
It has $N$ towns, numbered $1,2,\dots,N$. Town $i$ is at $(x_i, y_i)$, and no two different towns are at the same coordinates.

There are teleportation spells in the nation. A spell is identified by a pair of integers $(a,b)$, and casting a spell $(a, b)$ at coordinates $(x, y)$ teleports you to $(x+a, y+b)$.

Snuke is a great magician who can learn the spell $(a, b)$ for any pair of integers $(a, b)$ of his choice. The number of spells he can learn is also unlimited.
To be able to travel between the towns using spells, he has decided to learn some number of spells so that it is possible to do the following for every pair of different towns $(i, j)$.

• Choose just one spell among the spells learned. Then, repeatedly use just the chosen spell to get from Town $i$ to Town $j$.

At least how many spells does Snuke need to learn to achieve the objective above?

Constraints

• $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$.

Input

Input is given from Standard Input in the following format:

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

Output

Print the minimum number of spells Snuke needs to learn.

Sample Input 1

3
1 2
3 6
7 4

Sample Output 1

6

The figure below illustrates the positions of the towns (along with the coordinates of the four corners).

If Snuke learns the six spells below, he can get from Town $i$ to Town $j$ by using one of the spells once for every pair $(i,j)$ $(i \neq j)$, achieving his objective.

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

Another option is to learn the six spells below. In this case, he can get from Town $i$ to Town $j$ by using one of the spells twice for every pair $(i,j)$ $(i \neq j)$, achieving his objective.

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

There is no combination of spells that consists of less than six spells and achieve the objective, so we should print $6$.

Sample Input 2

3
1 2
2 2
4 2

Sample Output 2

2

The optimal choice is to learn the two spells below:

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

Sample Input 3

4
0 0
0 1000000000
1000000000 0
1000000000 1000000000

Sample Output 3

8

问题描述

阿特科德共和国位于一个笛卡尔坐标平面上。它有$N$个城镇，编号为$1,2,\dots,N$。城镇$i$位于$(x_i, y_i)$，且没有两个不同的城镇位于相同的坐标上。

国家内有瞬移咒语。一个咒语由一对整数$(a,b)$标识，施放一个$(a, b)$咒语在坐标$(x, y)$会将你传送到$(x+a, y+b)$。

斯努克是一位伟大的魔法师，他可以学习任意一对整数$(a, b)$的咒语。他能学习的咒语数量也是无限的。

为了能够使用咒语在城镇之间旅行，他决定学习一些数量的咒语，以便对于每一对不同的城镇$(i, j)$都能做到以下几点。

• 从学习的咒语中选择仅一个咒语。然后，仅使用选择的咒语从城镇$i$到达城镇$j$。

斯努克需要学习至少多少个咒语才能实现上述目标？

限制条件

• $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)$。

输入

输入从标准输入按以下格式给出：

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

输出

打印斯努克需要学习的咒语的最小数量。

样例输入1

3
1 2
3 6
7 4

样例输出1

6

下图展示了城镇的位置（以及四个角的坐标）。

如果斯努克学习了以下六个咒语，他可以通过对每一对$(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$。

样例输入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