Score : $400$ points

问题陈述

在AtCoder共和国中，国家位于笛卡尔坐标平面上。
它拥有$N$个城镇，分别编号为$1,2,\dots,N$。第$i$个城镇位于坐标$(x_i, y_i)$处，并且没有两个不同的城镇位于相同的坐标。

该国有着传送法术。一个法术由一对整数$(a,b)$标识，在坐标$(x, y)$处施放法术$(a, b)$会将你传送到坐标$(x+a, y+b)$的位置。

Snuke是一位伟大的魔法师，他可以选择学习任意整数对$(a, b)$的法术。他可以学习的法术数量也是无限的。
为了能够使用法术在各个城镇之间旅行，他决定学习一些法术，使得对于每一对不同的城镇$(i, j)$，都能够做到以下操作：

• 仅从已学习的法术中选择一个法术，然后仅重复使用所选的法术从城镇$i$到达城镇$j$。

至少需要学习多少个法术，Snuke才能实现上述目标？

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 09:55:25