/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 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
出力
すぬけ君が覚える必要がある魔法の個数の最小値を出力せよ。
入力例 1
3 1 2 3 6 7 4
出力例 1
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 を出力します。
入力例 2
3 1 2 2 2 4 2
出力例 2
2
次の 2 種類の魔法を覚えるのが最適です。
- (1, 0)
- (-1, 0)
入力例 3
4 0 0 0 1000000000 1000000000 0 1000000000 1000000000
出力例 3
8
Score : 400 points
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