← 返回题目列表

AtCoder · agc051_e

E. 中点

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

分数: 2000 点

问题陈述

最初, N 点 (x_1, y_1), \ldots, (x_N, y_N) 绘制在平面上。 Snuke 可以执行任意有限次数的以下操作:

  • 选择已绘制的两个点,并绘制两个所选点的中间点(如果尚未绘制中间点)。中点的坐标不一定必须是整数。

当他完成操作后,他的分数是具有整数坐标的绘制点的数量(包括初始点)。 计算他可以获得的最高分数。

约束

  • 3 \leq N \leq 100
  • 0 \leq x_i, y_i \leq 10^9
  • 没有三个点在同一条线上。
  • 输入中的所有值都是整数。

输入

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

N
x_1 y_1
:
x_N y_N

输出

打印答案。


示例输入 1

4
0 0
0 2
2 0
2 2

示例输出 1

9

获得最高分数的一种可能方法如下:

  • 最初,四点 绘制了 (0, 0), (0, 2), (2, 0), (2, 2) 。
  • 情节 (0, 1): 的中点 (0, 0) 和 (0, 2).
  • 情节 (0, 0.5): 的中点 (0, 0) 和 (0, 1).
  • 情节 (1, 0): 的中点 (0, 0) 和 (2, 0).
  • 情节 (1, 1): 的中点 (0, 0) 和 (2, 2).
  • 情节 (1, 2): 的中点 (0, 2) 和 (2, 2).
  • 情节 (2, 1): 的中点 (2, 0) 和 (2, 2).
  • 现在我们有 10 点: 其中 (0, 0), (0, 0.5), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2). 9 的坐标为整数,因此得分为 9.

示例输入 2

4
0 0
0 3
3 0
3 3

示例输出 2

4

我们可以证明,除了初始点之外,他无法绘制任何具有整数坐标的点。