传送

题目描述

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 至少需要学会多少个魔法才能达成上述目标?

输入格式

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

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

输出格式

输出 Snuke 需要学会的最少魔法数。

样例

3
1 2
3 6
7 4

6

如果 Snuke 学会下面六个魔法,那么对每一对 $(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$。

3
1 2
2 2
4 2

2

最优选择是学会下面两个魔法:

$(1, 0)$

$(-1, 0)$

4
0 0
0 1000000000
1000000000 0
1000000000 1000000000

8

数据范围

• $2 \le N \le 500$
• $0 \le x_i \le 10^9$($1 \le i \le N$)
• $0 \le y_i \le 10^9$($1 \le i \le N$)
• 当 $i \neq j$ 时,$(x_i, y_i) \neq (x_j, y_j)$。