← 返回题目列表

AtCoder · diverta2019_2_b

B. 拾取

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

有 N 二维平面中的球。 i- 第一个球位于坐标处 (x_i, y_i).

我们将通过选择两个整数来收集所有这些球 p 和 q 这样 p \neq 0 or q \neq 0 然后重复以下操作:

  • 选择飞机上剩余的一个球并收集它。让 (a, b) 是这个球的坐标。如果我们在坐标处收集一个球 (a - p, b - q) 在之前的操作中,本次操作的成本是 0。否则,包括第一次做这个操作时,这个操作的成本是 1.

找到当我们最优选择时收集所有球所需的最小总成本 p 和 q.

约束

  • 1 \leq N \leq 50
  • |x_i|, |y_i| \leq 10^9
  • If i \neq j, x_i \neq x_j or y_i \neq y_j.
  • 输入中的所有值都是整数。

输入

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

N
x_1 y_1
:
x_N y_N

输出

打印收集所有球所需的最低总成本。


示例输入 1

2
1 1
2 2

示例输出 1

1

如果我们选择 p = 1, q = 1,我们可以收集所有球,成本为 1 按顺序收集 (1, 1), (2, 2).


示例输入 2

3
1 4
4 6
7 8

示例输出 2

1

如果我们选择 p = -3, q = -2,我们可以收集所有球,成本为 1 按顺序收集 (7, 8), (4, 6), (1, 4).


示例输入 3

4
1 1
1 2
2 1
2 2

示例输出 3

2