题目描述

AtCoder 国は無限に広がる直交座標の上にあります。
AtCoder 国には $N$ 個の街があり、 $1,2,\dots,N$ と番号が付けられています。街 $i$ は地点 $(x_i,\ y_i)$ にあり、$2$ つの異なる番号の街が同じ座標にあることはありません。

AtCoder 国には転移魔法(以下、魔法と表記)があります。魔法は整数の組 $(a,b)$ によって識別されていて、地点 $(x,y)$ にいるときに魔法 $(a,b)$ を使うと $(x+a,y+b)$ にワープすることができます。

すぬけ君は、任意の整数の組 $(a,b)$ を選んで魔法 $(a,b)$ を覚えることができる大魔術師です。また、すぬけ君は何種類でも魔法を覚えることができます。
魔法を使って街と街の間を移動したくなったすぬけ君は、全ての相異なる街の組 $(i,j)$ について次の行動を取れるようにいくつかの魔法を覚えることにしました。

• 覚えた魔法のうち $1$ 種類の魔法のみ を選ぶ。その後、選んだ魔法 のみ を繰り返し使って街 $i$ から 街 $j$ に移動する。

すぬけ君が上の条件を満たすように魔法を覚えるとき、少なくとも何種類の魔法を覚えればよいですか？

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

すぬけ君が覚える必要がある魔法の個数の最小値を出力せよ。

题目大意

题目描述

AtCoder国家位于无限多的笛卡尔坐标上。

AtCoder国家有 $N$ 个城镇，编号为 $1,2,...,N$。

镇i位于点$(x_i,y_i)$，没有两个不同编号的镇可以在同一坐标上。 AtCoder国家有过渡魔法 (以下简称魔法）。

魔法由一对整数 $(a,b)$ 标识，如果你在点 $(x,y)$ 并使用魔法 $(a,b)$，你可以穿越到 $(x+a，y+b)$。

有一个伟大的魔术师（以下简称魔法师），他可以选择任何一对整数 $(a,b)$ 并学习魔术 $(a,b)$。 魔法师还可以学习任何数量的不同种类的魔法。

当他想用魔法从一个城市移动到另一个城市时，他决定学习一些魔法，这样他就可以对所有一对 $(i,j)$ 不同的城市进行以下操作。

在你所学的魔法中只选择一种类型的魔法时，就只能重复使用所选的魔法，从城市 $i$ 移动到城市 $j$。

为了满足上述条件，魔法师至少要学会多少种不同的魔法？

输入格式

第 1 行输入一个数 $N$.

第 2 行至第 N+1 行每行输入两个数 $x_i,y_i$

输出格式

输出大魔法师至少需要学习的魔法数。

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)$
• $i\ \neq\ j$ ならば $(x_i,\ y_i)\ \neq\ (x_j,\ y_j)$ である。

Sample Explanation 1

AtCoder 国の街の位置を図示したのが下の図です。(わかりやすさのために四隅の座標を表示しています。)  すぬけ君は次の $6$ 種類の魔法を覚えれば、すべての $(i,j)$ $(i\ \neq\ j)$ の組に対して街 $i$ から $1$ 種類の魔法を $1$ 回使うことで街 $j$ に着くことができるので条件を満たします。 - $(2,\ 4)$ - $(-2,\ -4)$ - $(4,\ -2)$ - $(-4,\ 2)$ - $(-6,\ -2)$ - $(6,\ 2)$ 次の $6$ 種類の魔法も条件を満たします。このときすぬけ君は、すべての $(i,j)$ $(i\ \neq\ j)$ の組に対して街 $i$ から $1$ 種類の魔法を $2$ 回使うことで街 $j$ に着くことができます。 - $(1,\ 2)$ - $(-1,\ -2)$ - $(2,\ -1)$ - $(-2,\ 1)$ - $(-3,\ -1)$ - $(3,\ 1)$ 条件を満たす魔法の組み合わせのうち $6$ 種類より少ないものは存在しないので、 $6$ を出力します。

Sample Explanation 2

次の $2$ 種類の魔法を覚えるのが最適です。 - $(1,\ 0)$ - $(-1,\ 0)$