← 返回题目列表

AtCoder · abc226_d

G. 传送

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

分数: 400 点

问题陈述

AtCoder 共和国位于笛卡尔坐标平面上。
它有 N 城镇,编号 1,2,\dots,N。镇 i 位于 (x_i, y_i),并且没有两个不同的城镇位于同一坐标。

这个国家有传送法术。咒语由一对整数来标识 (a,b),并施展咒语 坐标 (a, b) 在坐标处 (x, y) 将你传送到 (x+a, y+b).

Snuke是一位伟大的魔法师,可以学习咒语 (a, b) 对于任何整数对 (a, b) 他的选择。他可以学习的法术数量也是无限的。
为了能够使用法术在城镇之间旅行,他决定学习一定数量的法术,以便可以对每对不同的城镇执行以下操作 (i, j).

  • 选择 只需一个咒语 在所学的法术之中。然后反复使用 只是 从城镇获得的所选咒语 i 到镇 j.

Snuke至少需要学习多少法术才能达到上述目标?

约束

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

输入

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

N
x_1 y_1
x_2 y_2
\vdots
x_N y_N

输出

打印 Snuke 需要学习的最少法术数量。


示例输入 1

3
1 2
3 6
7 4

示例输出 1

6

下图显示了城镇的位置(以及四个角的坐标)。

image

如果斯努克学习了以下六个咒语,他可以从城镇中获得 i 到镇 j 每对使用其中一个法术一次 (i,j) (i \neq j),实现了他的目标。

  • (2, 4)
  • (-2, -4)
  • (4, -2)
  • (-4, 2)
  • (-6, -2)
  • (6, 2)

另一种选择是学习以下六个咒语。在这种情况下,他可以从 Town i 到镇 j 每对使用其中一个法术两次 (i,j) (i \neq j),实现了他的目标。

  • (1, 2)
  • (-1, -2)
  • (2, -1)
  • (-2, 1)
  • (-3, -1)
  • (3, 1)

没有少于六个咒语的咒语组合可以实现目标,因此我们应该打印 6.


示例输入 2

3
1 2
2 2
4 2

示例输出 2

2

最佳选择是学习以下两个法术:

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

示例输入 3

4
0 0
0 1000000000
1000000000 0
1000000000 1000000000

示例输出 3

8