AT_diverta2019_2_b.Picking Up

在二维平面上有 $N$ 个球，第 $i$ 个球位于 $(x_i,\ y_i)$。

首先，选择两个整数 $p,\ q$，要求 $p \neq 0$ 或 $q \neq 0$，然后重复以下操作，直到收集完所有球：

• 选择一个尚未收集的球并收集，设该球坐标为 $(a,\ b)$。如果上一个被收集的球的坐标是 $(a - p,\ b - q)$，则本次操作的代价为 $0$，否则代价为 $1$。对于第一个被收集的球，代价总是 $1$。

请计算，在最优选择 $p,\ q$ 的情况下，收集所有球所需代价的最小值。

输入通过标准输入给出，格式如下：

$N$ $x_1$ $y_1$ $:$ $x_N$ $y_N$

输出收集所有球所需代价的最小值。

限制条件

• $1 \leq N \leq 50$
• $|x_i|,\ |y_i| \leq 10^9$
• $x_i \neq x_j$ 或 $y_i \neq y_j\ (i \neq j)$
• 输入均为整数

样例解释 1

当 $p = 1,\ q = 1$ 时，可以按 $(1,\ 1)$、$(2,\ 2)$ 的顺序收集球，总代价为 $1$。

样例解释 2

当 $p = -3,\ q = -2$ 时，可以按 $(7,\ 8)$、$(4,\ 6)$、$(1,\ 4)$ 的顺序收集球，总代价为 $1$。

由 ChatGPT 4.1 翻译