配点 : $400$ 点

問題文

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$ に移動する。

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

制約

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

出力

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

3
1 2
3 6
7 4

6

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$ を出力します。

3
1 2
2 2
4 2

2

次の $2$ 種類の魔法を覚えるのが最適です。

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

4
0 0
0 1000000000
1000000000 0
1000000000 1000000000

8